Submission #213076

#TimeUsernameProblemLanguageResultExecution timeMemory
213076iris2617Arranging Shoes (IOI19_shoes)C++14
50 / 100
265 ms280132 KiB
#include "shoes.h" #include <queue> using namespace std; int arr[100010],n; queue<int> q[100010],q2[100010]; int bit[100010]; bool used[100010]; void build() { int i; for(i=1;i<=n;i++) { if(i+(i&(-i))<=n) { bit[i+(i&(-i))]+=bit[i]; } } } void add(int a,int k) { int i; for(i=a;i<=n;i+=(i&(-i))) { bit[i]+=k; } } int sum(int a) { int i,res=0; for(i=a;i;i-=(i&(-i))) { res+=bit[i]; } return res; } long long count_swaps(std::vector<int> s) { int i,ans,a; ans=0; n=s.size(); for(i=1;i<=n;i++) { a=s[i-1]; if(a<0) { q[-a].push(i); } else { q2[a].push(i); } arr[i]=a; bit[i]=1; } build(); for(i=1;i<=n;i++) { if(used[i]) { continue; } used[i]=1; if(arr[i]>0) { add(q[arr[i]].front(),-1); add(i,-1); ans+=sum(q[arr[i]].front())+1; used[q[arr[i]].front()]=1; } else { arr[i]*=-1; add(q2[arr[i]].front(),-1); add(i,-1); ans+=sum(q2[arr[i]].front()); used[q2[arr[i]].front()]=1; } q[arr[i]].pop(); q2[arr[i]].pop(); } 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...