Test/AtCoder/abc261_f.test.cpp

View this file on GitHub
Last update: 2024-07-09 03:03:14+09:00
Problem: https://atcoder.jp/contests/abc261/tasks/abc261_f

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc261/tasks/abc261_f"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Sequence/InversionNumber.hpp"

#include <iostream>
#include <vector>

using namespace zawa;

int main() {
    SetFastIO(); 
    int N;
    std::cin >> N;
    std::vector<int> C(N), X(N);
    for (int& c : C) {
        std::cin >> c;
        c--;
    }
    std::vector<std::vector<int>> A(N);
    for (int i{} ; i < N ; i++) {
        std::cin >> X[i];
        A[C[i]].push_back(X[i]);
    }
    long long ans{(long long)InversionNumber(X.begin(), X.end())};
    for (int i{} ; i < N ; i++) {
        ans -= InversionNumber(A[i].begin(), A[i].end());
    }
    std::cout << ans << '\n';
}

#line 1 "Test/AtCoder/abc261_f.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc261/tasks/abc261_f"

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/Sequence/InversionNumber.hpp"

#line 4 "Src/Sequence/InversionNumber.hpp"

#include <cassert>
#include <iterator>
#include <type_traits>
#include <vector>

namespace zawa {

template <class InputIterator>
u64 InversionNumber(InputIterator first, InputIterator last) {
    assert((usize)std::distance(first, last) >= usize{0});
    std::vector<std::remove_reference_t<decltype(*first)>> A(first, last);
    auto rec{[&](auto rec, usize L, usize R) -> u64 {
        if (R - L <= usize{1}) return 0; 
        usize M{(L + R) >> 1};
        u64 res{rec(rec, L, M) + rec(rec, M, R)};
        std::vector<u64> tmp(R - L);
        usize i{L}, j{M}, k{};
        while (i < M and j < R) {
            if (A[i] <= A[j]) {
                tmp[k++] = A[i++];
            }
            else {
                res += M - i;
                tmp[k++] = A[j++];
            }
        }
        while (i < M) tmp[k++] = A[i++];
        while (j < R) tmp[k++] = A[j++];
        for (usize l{L} ; l < R ; l++) {
            A[l] = tmp[l - L];
        }
        return res;
    }};
    return rec(rec, usize{0}, usize{A.size()});
}

template <class InputIterator>
bool InversionParity(InputIterator first, InputIterator last) {
    assert((usize)std::distance(first, last) >= usize{0});
    std::vector<std::remove_reference_t<decltype(*first)>> A(first, last);
    auto rec{[&](auto rec, usize L, usize R) -> bool {
        if (R - L <= usize{1}) return 0; 
        usize M{(L + R) >> 1};
        bool res{rec(rec, L, M) != rec(rec, M, R)};
        std::vector<u64> tmp(R - L);
        usize i{L}, j{M}, k{};
        while (i < M and j < R) {
            if (A[i] <= A[j]) {
                tmp[k++] = A[i++];
            }
            else {
                res ^= (M - i) & 1;
                tmp[k++] = A[j++];
            }
        }
        while (i < M) tmp[k++] = A[i++];
        while (j < R) tmp[k++] = A[j++];
        for (usize l{L} ; l < R ; l++) {
            A[l] = tmp[l - L];
        }
        return res;
    }};
    return rec(rec, usize{0}, usize{A.size()});
}

} // namespace zawa
#line 5 "Test/AtCoder/abc261_f.test.cpp"

#line 8 "Test/AtCoder/abc261_f.test.cpp"

using namespace zawa;

int main() {
    SetFastIO(); 
    int N;
    std::cin >> N;
    std::vector<int> C(N), X(N);
    for (int& c : C) {
        std::cin >> c;
        c--;
    }
    std::vector<std::vector<int>> A(N);
    for (int i{} ; i < N ; i++) {
        std::cin >> X[i];
        A[C[i]].push_back(X[i]);
    }
    long long ans{(long long)InversionNumber(X.begin(), X.end())};
    for (int i{} ; i < N ; i++) {
        ans -= InversionNumber(A[i].begin(), A[i].end());
    }
    std::cout << ans << '\n';
}