Submission #250014

#TimeUsernameProblemLanguageResultExecution timeMemory
250014DavidDamianArranging Shoes (IOI19_shoes)C++14
100 / 100
465 ms149624 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll bit[400005]; ll query(int i) { ll sum=0; while(i>0){ sum+=bit[i]; i-=i&(-i); } return sum; } ll getSum(int a,int b) { return query(b)-query(a-1); } void update(int n,int i,ll v) { while(i<=n){ bit[i]+=v; i+=i&(-i); } } map<int,queue<int> > pairing; int link[400005]; ll count_swaps(vector<int> s) { int n=s.size(); for(int i=0;i<n;i++){ if(pairing[ -s[i] ].empty()){ pairing[ s[i] ].push(i); } else{ int id=pairing[ -s[i] ].front(); pairing[ -s[i] ].pop(); link[id]=i; link[i]=id; } } int c=0; for(int i=0;i<n;i++){ if(link[i]<i) continue; if(s[i]<0) s[i]=++c, s[ link[i] ]=++c; else s[ link[i] ]=++c, s[i]=++c; } ll total=0; for(int i=0;i<n;i++){ total+=getSum(s[i]+1,n+1); update(n+1,s[i],1); } return total; }
#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...