結果
問題 |
No.1604 Swap Sort:ONE
|
ユーザー |
|
提出日時 | 2021-07-19 11:16:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 952 bytes |
コンパイル時間 | 1,830 ms |
コンパイル使用メモリ | 172,920 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-16 19:25:48 |
合計ジャッジ時間 | 2,447 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
//#include <atcoder/all> #include <bits/stdc++.h> using namespace std; //using namespace atcoder; using ll = long long; #define all(A) A.begin(),A.end() using vll = vector<ll>; #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) using Graph = vector<vector<pair<ll, ll>>>; Graph G; vll dist; vector<bool> seen; struct fenwick_tree { ll n; vll bit; fenwick_tree(ll num) :bit(num + 1, 0) { n = num; } void add(ll i, ll w) { for (ll x = i+1; x <= n; x += x & -x) { bit[x-1] += w; } } ll sum(ll i) { ll ret = 0; for (ll x = i+1; x > 0; x -= x & -x) { ret += bit[x-1]; } return ret; } ll sum(ll L, ll R) { return sum(R) - sum(L); } }; ll TE(vll A) { ll res = 0; ll N = A.size(); fenwick_tree fw(N); rep(i, N) { res += i - fw.sum(A[i]); fw.add(A[i], 1); } return res; } int main() { ll N; cin>>N; vll P(N); rep(i,N){ cin>>P[i]; P[i]--; } cout<<TE(P)<<endl; }