제출 #155759

#제출 시각아이디문제언어결과실행 시간메모리
155759gurkotArranging Shoes (IOI19_shoes)C++14
50 / 100
1061 ms138924 KiB
#include <cstdio> #include <cassert> #include <queue> #include <vector> #include <iostream> using namespace std; struct Q{int x,npair;}; queue <Q> q[100001]; Q qin,qout; int n; int s[100001]; int prev(int u){ return u&(u-1); } int next(int u){ return (u<<1)-(u&(u-1)); } int getsum(int a, int b){ if (a>b) return 0; int ans=0; while (b>0){ ans+=s[b]; b=prev(b); } a--; while (a>0){ ans-=s[a]; a=prev(a); } return ans; } void update(int pos, int x){ while (pos<=n){ s[pos]+=x; pos=next(pos); } } long long count_swaps(std::vector<int> a) { long long ans=0; int x,mx,npair=0; n=a.size(); for (int i=0;i<n;i++){ x=mx=a[i]; if (mx<0) mx=-mx; if (q[mx].size()==0) { npair++; qin.x=x; qin.npair=npair; q[mx].push(qin); update(npair,1); //cout<<"i="<<i<<" update "<<npair<<"<=1"<<endl; } else { qout=q[mx].front(); if (qout.x==x) { npair++; qin.x=x; qin.npair=npair; q[mx].push(qin); update(npair,1); //cout<<"i="<<i<<" update (same x) "<<npair<<"<=1"<<endl; } else { int old_npair=qout.npair; ans+=getsum(old_npair+1,npair); if (x<0) ans++; update(old_npair,1); //cout<<"i="<<i<<" update oldpair (same x) "<<old_npair<<"<=+1(2)"<<endl; q[mx].pop(); } }//size()>0 }//i 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...