제출 #802225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802225		Benmath	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	73 ms	16852 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=query(1,0,2*n-1,i,2*n-1);
       int x2=query(1,0,2*n-1,i+1,2*n-1);
       int tren1=s[i-x1];
       int tren2=s[i+1-x2];
       if((tren1+tren2)!=0){
           int ind;
           if(tren1>0){
               ind=vneg[tren1][roneg[tren1]];
               roneg[tren1]++;
           }else{
               ind=vpos[abs(tren1)][ropos[abs(tren1)]];
               ropos[abs(tren1)]++;
           }    int ind1=ind;
           if(ind!=(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,ind1,1);
       }
       if(tren1>0){
           sum++;
       }
     
   }
  return sum;
   
}

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