結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 2019-03-23 15:20:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 697 ms / 3,000 ms |
コード長 | 1,776 bytes |
コンパイル時間 | 1,986 ms |
コンパイル使用メモリ | 207,824 KB |
最終ジャッジ日時 | 2025-01-07 00:18:22 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; template<typename T> vector<T> compress(vector<T> v){ sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return v; } template<typename T> map<T, Int> dict(const vector<T> &v){ map<T, Int> res; for(Int i=0;i<(Int)v.size();i++) res[v[i]]=i; return res; } template<typename T> struct BIT{ Int n; vector<T> bit; //1-indexed BIT():n(-1){} BIT(Int n_,T d):n(n_),bit(n_+1,d){} T sum(Int i){ T s=bit[0]; for(Int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } void add(Int i,T a){ if(i==0) return; for(Int x=i;x<=n;x+=(x&-x)) bit[x]+=a; } Int lower_bound(Int w){ if(w<=0) return 0; Int x=0,r=1; while(r<n) r<<=1; for(Int k=r;k>0;k>>=1){ if(x+k<=n&&bit[x+k]<w){ w-=bit[x+k]; x+=k; } } return x+1; } T sum0(Int i){ return sum(i+1); } void add0(Int i,T a){ add(i+1,a); } T query(Int l,Int r){ return sum(r-1)-sum(l-1); } T query0(Int l,Int r){ return sum(r)-sum(l); } }; //INSERT ABOVE HERE signed main(){ Int n; cin>>n; vector<Int> a(n); for(Int i=0;i<n;i++) cin>>a[i]; auto c=compress(a); auto d=dict(c); for(Int &x:a) x=d[x]; BIT<Int> bit(n,0); Int cnt=0; for(Int i=0;i<n;i++){ cnt+=i-bit.sum0(a[i]); bit.add0(a[i],1); } for(Int i=0;i<n;i++){ cout<<cnt<<"\n"; cnt-=bit.sum0(a[i]-1); cnt+=n-bit.sum0(a[i]); } cout<<flush; return 0; }