Submission #155762

#	Time	Username	Problem	Language	Result	Execution time	Memory
155762		gurkot	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	247 ms	139228 KiB

shoes

#include <cstdio>
#include <cassert>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;

struct Q{int x,npair;};
queue <Q> q[200001];
Q qin,qout;

int n;
int s[200001];

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;	
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15