제출 #638121

#제출 시각아이디문제언어결과실행 시간메모리
638121JJAnawatArranging Shoes (IOI19_shoes)C++14
50 / 100
53 ms27112 KiB
#include "shoes.h" #include<bits/stdc++.h> using namespace std; bool chk[100005]; vector<int> pl[100005],pr[100005]; int fw[100005]; void up(int x,int v){ for(int i=x;i<100005;i+=i&-i) fw[i]+=v; } long long qr(int x){ long long sum=0; for(int i=x;i>0;i-=i&-i) sum+=fw[i]; return sum; } long long count_swaps(vector<int> s) { int n=s.size(); for(int i=n-1;i>=0;i--){ if(s[i]>0) pr[s[i]].push_back(i); else pl[-s[i]].push_back(i); } long long ans=0; for(int i=0;i<n;i++){ if(chk[i]) continue; int sz=abs(s[i]); if(s[i]>0){ int pos=pl[sz].back(); chk[pos]=chk[i]=1; pl[sz].pop_back(); pr[sz].pop_back(); ans+=pos-i-(qr(pos)-qr(i)); up(pos,1); } else{ int pos=pr[sz].back(); chk[pos]=chk[i]=1; pl[sz].pop_back(); pr[sz].pop_back(); ans+=pos-i-1-(qr(pos)-qr(i)); up(pos,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...