Submission #936861

#TimeUsernameProblemLanguageResultExecution timeMemory
9368614QT0RArranging Shoes (IOI19_shoes)C++17
100 / 100
137 ms142448 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long queue<int> pos[200004]; const int base=1<<18; ll tree[2*base]; void zmien(int v){ v+=base; tree[v]^=1; v>>=1; while(v){ tree[v]=tree[2*v]+tree[2*v+1]; v>>=1; } } ll sprawdz(int l, int p){ l+=base-1; p+=base+1; ll ans=0; while(l/2!=p/2){ if (!(l&1))ans+=tree[l+1]; if (p&1)ans+=tree[p-1]; l>>=1; p>>=1; } return ans; } ll count_swaps(vector<int> S){ ll n=S.size(),open=0,odp=0; for (int i = 0; i<n; i++){ if (S[i]>0){ if (pos[S[i]+100000].empty()){ pos[S[i]].push(i); zmien(i); } else{ odp+=i-pos[S[i]+100000].front()-1; odp-=sprawdz(pos[S[i]+100000].front()+1,i); zmien(pos[S[i]+100000].front()); pos[S[i]+100000].pop(); } } else{ if (pos[-S[i]].empty()){ pos[100000-S[i]].push(i); zmien(i); } else{ odp+=i-pos[-S[i]].front(); odp-=sprawdz(pos[-S[i]].front()+1,i); zmien(pos[-S[i]].front()); pos[-S[i]].pop(); } } } return odp; }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:33:16: warning: unused variable 'open' [-Wunused-variable]
   33 |  ll n=S.size(),open=0,odp=0;
      |                ^~~~
#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...