제출 #204122

#제출 시각아이디문제언어결과실행 시간메모리
204122medkArranging Shoes (IOI19_shoes)C++14
0 / 100
1080 ms256 KiB
#include <bits/stdc++.h> #include "shoes.h" #define ll long long #define pb push_back #define x first #define y second using namespace std; int n; vector<int> a,bit; vector<vector<int>> pos; void update(int x, int val) { for(;x<=n;x+=x&-x) bit[x]+=val; } ll pre(int x) { ll ret=0; for(;x>0;x-=x&-x) ret+=bit[x]; return ret; } ll sm(int l, int r) { return pre(r)-pre(l-1); } ll count_swaps(vector<int> S) { ll ans=0; n=S.size(); bit.resize(n+1); a.pb(0); for(int i=1;i<=n;i++) a.pb(1), update(i,1); pos.resize(n/2+1); for(int i=0;i<n;i++) pos[S[i]].pb(i+1); vector<int> pt(n/2+1,0); for(int i=1;i<=n;i++) { if(a[i]==0) continue; ans+=sm(i+1,pos[S[i-1]][pt[S[i-1]]+1]-1); a[i]=0, a[pos[S[i-1]][pt[S[i-1]]+1]]=0; update(i,-1), update(pos[S[i-1]][pt[S[i-1]]+1],-1); pt[S[i-1]]+=2; } 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...