結果
問題 |
No.1604 Swap Sort:ONE
|
ユーザー |
![]() |
提出日時 | 2021-07-17 00:00:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 740 bytes |
コンパイル時間 | 1,784 ms |
コンパイル使用メモリ | 195,880 KB |
最終ジャッジ日時 | 2025-01-23 02:50:15 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#define rep(i, n) for (int i = 0; i < (int)(n); i++) #define ALL(v) v.begin(), v.end() typedef long long ll; #include <bits/stdc++.h> using namespace std; template<typename T> struct BIT{ private: vector<T> A; const int n; public: BIT(int _n) : A(_n+1,0), n(_n){} T sum(int i){ T s=0; while(i>0){ s+=A[i]; i-=i&-i; } return s; } T sum(int i,int j){ return sum(j)-sum(i-1); } void add(int i,T x){ while(i<=n){ A[i]+=x; i+=i&-i; } } }; int main(){ int n; cin>>n; BIT<int> bit(n); vector<int> A(n); rep(i,n) cin>>A[i]; ll ans=0; for(int j=0;j<n;j++){ ans+=j-bit.sum(A[j]); bit.add(A[j],1); } cout<<ans<<endl; return 0; }