結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
![]() |
提出日時 | 2020-08-05 22:39:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,235 bytes |
コンパイル時間 | 1,563 ms |
コンパイル使用メモリ | 171,608 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-17 16:05:58 |
合計ジャッジ時間 | 4,026 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 28 WA * 7 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<long long> vl; #define INF __INT32_MAX__ #define LINF __LONG_LONG_MAX__ class BIT { private: vi node; int n; public: BIT(int n_) { n = n_; node.resize(n + 1); } void add(int i, int x) { while (i <= n) { node[i] += x; i += (i & (-i)); } } int sum(int i) { int sum = 0; while (i > 0) { sum += node[i]; i -= (i & (-i)); } return sum; } int sum(int a, int b) { return sum(b) - sum(a - 1); } }; int main() { int N; cin >> N; vi A(N + 1), B(N + 1); rep(i, N) { cin >> A[i]; } rep(i, N) { cin >> B[i]; } vi conv(N + 1); rep(i, N) { conv[B[i]] = i + 1; } rep(i, N) { A[i] = conv[A[i]]; } int cnt = 0; BIT bit(N); rep(i, N) { bit.add(A[i], 1); cnt += (i + 1) - bit.sum(A[i]); } cout << cnt << endl; }