Submission #1267609

#TimeUsernameProblemLanguageResultExecution timeMemory
1267609zagaroArranging Shoes (IOI19_shoes)C++17
100 / 100
206 ms275840 KiB
#include<bits/stdc++.h> #include "shoes.h" typedef long long ll; using namespace std; ll count_swaps(vector<int> vec){ ll n, r=0, s=0, a, t, x, k; n = vec.size(); vector<queue<ll> > izq(n+1); vector<queue<ll> > der(n+1); vector<ll> prf(n+100, 0); vector<pair<ll,ll> > pr; for(int i=1;i<=n;i++){ t = abs(vec[i-1]); if(vec[i-1] < 0){ if(der[t].empty())izq[t].push(i); else { x = der[t].front(); r+= i-x; pr.push_back({x, i}); der[t].pop(); for(int k=x;k<=n;k+=(k&(-k)))prf[k]+=1; for(int k=i;k<=n;k+=(k&(-k)))prf[k]+= (-1); } } else { if(izq[t].empty())der[t].push(i); else { x = izq[t].front(); r+= i-x-1; pr.push_back({x, i}); izq[t].pop(); for(int k=x;k<=n;k+=(k&(-k)))prf[k]+=1; for(int k=i;k<=n;k+=(k&(-k)))prf[k]+= (-1); } } } sort(pr.begin(), pr.end()); for(int i=0;i<pr.size();i++){ a=0; for(int k=pr[i].second;k>=1;k-=(k&(-k)))a+=prf[k]; for(int k=pr[i].first;k<=n;k+=(k&(-k)))prf[k]+= (-1); for(int k=pr[i].second;k<=n;k+=(k&(-k)))prf[k]+= 1; s+=a; } return (r-s); }
#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...