結果
問題 | No.1282 Display Elements |
ユーザー |
![]() |
提出日時 | 2020-11-06 21:34:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 237 ms / 2,000 ms |
コード長 | 1,130 bytes |
コンパイル時間 | 1,905 ms |
コンパイル使用メモリ | 180,660 KB |
実行使用メモリ | 15,324 KB |
最終ジャッジ日時 | 2024-07-22 12:20:44 |
合計ジャッジ時間 | 4,289 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename T> struct binary_indexed_tree{ int N; vector<T> BIT; binary_indexed_tree(int n){ N = 1; while (N < n){ N *= 2; } BIT = vector<T>(N + 1, 0); } void add(int i, T x){ i++; while (i <= N){ BIT[i] += x; i += i & -i; } } T sum(int i){ T ans = 0; while (i > 0){ ans += BIT[i]; i -= i & -i; } return ans; } }; int main(){ int N; cin >> N; vector<int> a(N); for (int i = 0; i < N; i++){ cin >> a[i]; } sort(a.begin(), a.end()); vector<int> b(N); for (int i = 0; i < N; i++){ cin >> b[i]; } vector<int> x; for (int i = 0; i < N; i++){ x.push_back(a[i]); x.push_back(b[i]); } sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); int cnt = x.size(); map<int, int> mp; for (int i = 0; i < cnt; i++){ mp[x[i]] = i; } for (int i = 0; i < N; i++){ a[i] = mp[a[i]]; b[i] = mp[b[i]]; } long long ans = 0; binary_indexed_tree<int> BIT(cnt); for (int i = 0; i < N; i++){ BIT.add(b[i], 1); ans += BIT.sum(a[i]); } cout << ans << endl; }