Submission #797957

#TimeUsernameProblemLanguageResultExecution timeMemory
797957MularstyleArranging Shoes (IOI19_shoes)C++14
100 / 100
121 ms141392 KiB
#include<bits/stdc++.h> using namespace std; #include "shoes.h" #define ll long long int n; ll ar[200005]; bool vis[200005]; void up(int idx,int x) { while(idx<=n)ar[idx]+=x,idx+=(idx&-idx); } int re(int idx) { ll sum=0; while(idx>0)sum+=ar[idx],idx-=(idx&-idx); return sum; } long long count_swaps(std::vector<int> os) { ll ans=0; n=os.size(); int s[n+5]; for(int i=1;i<=n;i++) s[i]=os[i-1]; queue<int> S[n]; int pidx[n+5]; for(int i=1;i<=n;i++) { up(i,1); if(S[abs(s[i])].empty()) S[abs(s[i])].push(i); else { int tmp=S[abs(s[i])].front(); if(s[i]!=s[tmp])//pair { pidx[i]=tmp; pidx[tmp]=i; S[abs(s[i])].pop(); } else { S[abs(s[i])].push(i); } } } for(int i=1;i<=n;i++) { if(vis[pidx[i]])continue; vis[i]=1; // ans+=re(pidx[i]); ans+=( ( re(pidx[i])-re(i-1) ) -2 ); if(s[i]>0)//rightonleft ans++; up(i,-1); up(pidx[i],-1); } 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...