제출 #486896

#제출 시각아이디문제언어결과실행 시간메모리
486896HaidaraArranging Shoes (IOI19_shoes)C++17
10 / 100
145 ms113328 KiB
#include<bits/stdc++.h> #include<shoes.h> #define rep(i,x,n) for(int i=(x);i<(n);i++) #define FOR(i,n) rep(i,0,n) #define v(i) vector< i > #define ll long long #define pp push_back using namespace std; const ll inf=1LL<<62LL; const ll mod=1e9+7; const ll maxn=1000200; ll st[4*maxn]; int n; ll query(int ql,int qr,int l=1,int r=n,int inx=1) { if(ql<=l&&r<=qr) return st[inx]; if(ql>r||l>qr) return 0; int mid=l+(r-l)/2; return query(ql,qr,mid+1,r,inx*2+1)+query(ql,qr,l,mid,inx*2); } void update(int pos,int l=1,int r=n,int inx=1) { if(l==r) { st[inx]=0; return ; } int mid=l+(r-l)/2; if(mid<=pos) update(pos,l,mid,inx*2); else update(pos,mid+1,r,inx*2+1); st[inx]=st[inx*2]+st[inx*2+1]; } int build(int l=1,int r=n,int inx=1) { if(l==r) return st[inx]=1; int mid=l+(r-l)/2; return st[inx]=build(l,mid,inx*2)+build(mid+1,r,inx*2+1); } set <int> s[maxn*2]; ll count_swaps(v(int)vec) { v(int)a(maxn); n=vec.size(); rep(i,1,n+1) a[i]=vec[i-1]; rep(i,1,n+1) s[a[i]+n].insert(i); build(); ll ans=0; v(bool)vis(maxn,0); rep(i,1,n+1) { if(vis[i]) continue; ll poz=*s[-a[i]+n].begin(); s[a[i]+n].erase(i); s[-a[i]+n].erase(poz); ans+=query(i,poz)-2; if(a[i]>0) ans++; update(i); update(poz); vis[i]=vis[poz]=1; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...