Submission #836210

#TimeUsernameProblemLanguageResultExecution timeMemory
836210DenkataArranging Shoes (IOI19_shoes)C++14
65 / 100
257 ms419004 KiB
#include<bits/stdc++.h> #include "shoes.h" //#include "grader.cpp" using namespace std; const int maxn = 1e5; const int inf = 3e5+3; long long i,j,ans,p,q,b[inf],n; vector <int> v; deque <int> pos[inf]; void upd(int p) { while(p<=n) { b[p]++; p = (p|(p+1)); } } long long rsq(int p) { long long sum = 0; while(p>=0) { sum+=b[p]; p = ((p&(p+1))-1); } return sum; } long long count_swaps(vector<int> s) { ans = 0; j = 1; n = (int)s.size()*2; //memset(pos,-1,sizeof(pos)); for(auto i:s) { if(!pos[-i+maxn].empty()) { if(i>0) v.push_back(pos[-i+maxn].front()+1),pos[-i+maxn].pop_front(); else v.push_back(pos[-i+maxn].front()-1),pos[-i+maxn].pop_front(); } else { if(i>0) pos[i+maxn].push_back(j+1),v.push_back(j+1); else pos[i+maxn].push_back(j),v.push_back(j); } j+=2; } j = 0; for(auto i:v) { // cout<<i<<endl; ans+=j-rsq(i); upd(i); j++; } return ans; } /** 2 -2 -2 2 2 2 2 1 -1 -2 */
#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...