結果
問題 |
No.1604 Swap Sort:ONE
|
ユーザー |
![]() |
提出日時 | 2021-12-27 16:15:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,213 bytes |
コンパイル時間 | 1,845 ms |
コンパイル使用メモリ | 177,488 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-25 09:58:51 |
合計ジャッジ時間 | 2,925 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> class BIT{ public: int N; vector<T> data; BIT(T _N):N(_N){ data.assign(N+1, 0); }; // a is 1-indexed void add(int a, T w){ for(int x = a; x <= N; x += x & -x)data[x] += w; } // 1-indexed sum of prefix [0, a] T sum(int a){ T res = 0; for(int x = a; x > 0; x -= x & -x)res += data[x]; return res; } // 1-indexed sum of range [l, r] T sum(int l, int r){return sum(r) - sum(l-1);} // 0-indexed add void add0(int a, T w){add(a + 1, w);} // 0-indexed sum T sum0(int a){return sum(a + 1);} // 0-indexed sum of range T sum0(int l, int r){return sum0(r) - sum0(l-1);} // show the value void debug(){print(data);} }; int main() { int N; cin >> N; vector<pair<int, int>> ap( N ); for( int i = 0; i < N; i++ ) { int P; cin >> P; ap[i] = make_pair( P, i ); } sort( ap.begin(), ap.end() ); vector<int> b( N ); for( int i = 0; i < N; i++ ) b[ ap[i].second ] = i; BIT<long long> c( N ); long long ans = 0; for( int i = 0; i < N; i++ ) { ans += i - c.sum0( b[i] ); c.add0( b[i], 1 ); } cout << ans << endl; }