結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
|
提出日時 | 2022-03-20 18:56:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 3,164 bytes |
コンパイル時間 | 628 ms |
コンパイル使用メモリ | 70,600 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-07 05:58:09 |
合計ジャッジ時間 | 3,696 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <iostream>#include <vector>template <class T>struct BinaryIndexedTree {int N; // array lengthint power = 1; // minimum power of 2 larger than N (power = 2^i > N)std::vector<T> bit; // bit data arrayBinaryIndexedTree(int N = 0) : N(N) {bit.assign(N + 1, 0);while (power <= N)power <<= 1; // power > N}BinaryIndexedTree(const std::vector<T> &A) {N = (int)A.size();bit.assign(N + 1, 0);while (power <= N)power <<= 1; // power > N// buildfor (int i = 1; i <= N; ++i)add(i, A[i - 1]);}// add x to a[i]// constraint: 0 <= i < Nvoid add(int i, T x) {for (int idx = ++i; idx <= N; idx += (idx & -idx)) {bit[idx] += x;}}// sum(k) returns \sum_{0 <= i < k} a[i]// constraint: 0 <= k <= NT sum(int k) {T ret = 0;for (int idx = ++k; idx > 0; idx -= (idx & -idx)) {ret += bit[idx];}return ret;}// sum(l,r) returns \sum_{l <= i < r} a[i]// constraint: 0 <= l < r <= NT sum(int l, int r) {return sum(r) - sum(l - 1);}// lower_bound returns mininum index k s.t. \sum_{0 <= i <= k} >= x// constraint: a[i] >= 0 for all iint lower_bound(T x) {int k = 0;for (int r = power >> 1; r > 0; r >>= 1) {if (k + r <= N && bit[k + r] < x) {x -= bit[k + r];k += r;}}return k;}};// TODO:refactor BinaryIndexedTree2D// 1-indexedtemplate <class T>struct BinaryIndexedTree2D {int H, W;std::vector<std::vector<T>> bit;BinaryIndexedTree2D(int H = 0, int W = 0) : H(H), W(W) {bit.assign(H + 1, std::vector<T>(W + 1, 0));}// add x to a[h][w]void add(int h, int w, T x) {for (int i = h; i <= H; i += (i & -i)) {for (int j = w; j <= W; j += (j & -j)) {bit[i][j] += x;}}}// return sum of a[i][j] s.t. (1 <= i <= h and 1 <= j <= w)T sum(int h, int w) {T ret = 0;for (int i = h; i > 0; i -= (i & -i)) {for (int j = w; j > 0; j -= (j & -j)) {ret += bit[i][j];}}return ret;}// return sum of a[i][j] s.t. (h1 <= i < h2 and w1 <= j < w2)T query(int h1, int h2, int w1, int w2) {return sum(h2 - 1, w2 - 1) - sum(h2 - 1, w1 - 1) - sum(h1 - 1, w2 - 1) + sum(h1 - 1, w1 - 1);}};/*https://yukicoder.me/problems/no/1115*/int main() {int N;std::cin >> N;std::vector<int> A(N), B(N), C(N + 1);for (int i = 0; i < N; i++)std::cin >> A[i];for (int i = 0; i < N; i++)std::cin >> B[i];for (int i = 0; i < N; i++)C[B[i]] = i;for (int i = 0; i < N; i++)A[i] = C[A[i]];BinaryIndexedTree<int> bit(N);long long ans = 0;for (int i = 0; i < N; i++) {ans += i - bit.sum(A[i]);bit.add(A[i], 1);}std::cout << ans << '\n';return 0;}