Submission #802375

#	Time	Username	Problem	Language	Result	Execution time	Memory
802375		Benmath	Arranging Shoes (IOI19_shoes)	C++14	25 / 100	404 ms	14716 KiB

shoes

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/
//#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

int tree[800001];
void update(int node,int start,int end,int idx,int val){
    if(start==end){
        tree[node]+=val;
    }else{
        int mid=(start+end)/2;
        if(start<=idx and idx<=mid){
            update(2*node,start,mid,idx,val);
        }else{
            update(2*node+1,mid+1,end,idx,val);
        }
        tree[node]=tree[2*node]+tree[2*node+1];
    }
}
int query(int node,int start,int end,int l,int r){
    if(l<=start and end<=r){
        return tree[node];
    }
    if(r<start or end<l){
        return 0;
    }
    int mid=(start+end)/2;
    return query(2*node,start,mid,l,r)+query(2*node+1,mid+1,end,l,r);
}
long long count_swaps(std::vector<int> s) {
int n=s.size();
n=n/2;

   int ropos[n+1];
   int roneg[n+1];
   vector<int>vpos[n+1];
   vector<int>vneg[n+1];
   for(int i=0;i<=n;i++){
       ropos[i]=0;
       roneg[i]=0;
   }
   for(int i=0;i<2*n;i++){
   
       if(s[i]>0){
           vpos[s[i]].push_back(i);
       }else{
           vneg[abs(s[i])].push_back(i);
       }
   }
   long long int sum=0;
   for(int i=0;i<2*n;i=i+2){
      int x1=i;
      int x2=i+1;
      int l=0;
      int r=i;
      while(l<=r){
      	int mid=(l+r)/2;
      	int ro=query(1,0,2*n-1,mid,2*n-1)+mid;
      	if(ro>=i){
      		x1=min(x1,mid);
      		r=mid-1;
		  }else{
		  	l=mid+1;
		  }
	  }
	  l=0;
	  r=i+1;
	  while(l<=r){
      	int mid=(l+r)/2;
      	int ro=query(1,0,2*n-1,mid,2*n-1)+mid;
      	if(ro>=(i+1)){
      		x2=min(x2,mid);
      		r=mid-1;
		  }else{
		  	l=mid+1;
		  }
	  }
   
       int tren1=s[x1];
       int tren2=s[x2];
       if((tren1+tren2)!=0){
           int ind;
           if(tren1>0){
               ind=vneg[tren1][roneg[tren1]];
              
           }else{
               ind=vpos[abs(tren1)][ropos[abs(tren1)]];
              
           }    int ind1=ind;
           if(ind1!=(2*n-1)){
           
               ind=ind1+query(1,0,2*n-1,ind1+1,2*n-1);
           }
           
           sum=sum+(ind-(i+1));
           update(1,0,2*n-1,ind,1); 
        // cout<<sum<<" "<<tren1<<" "<<ind<<" "<<ind1<<" "<<query(1,0,2*n-1,0,2*n-1)<<" "<<endl;
       }
       ropos[abs(tren1)]++;
       roneg[abs(tren1)]++;
       if(tren1>0){
           sum++;
       }
      
     
   }
return sum;
   
}

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