Submission #916249

#	Time	Username	Problem	Language	Result	Execution time	Memory
916249		Aiperiii	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	191 ms	36592 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
const int N=2e5+5;
long long t[N*4];
void build(int v,int tl,int tr){
   if(tl==tr)t[v]=1;
   else{
      int tm=(tl+tr)/2;
      build(v*2,tl,tm);
      build(v*2+1,tm+1,tr);
      t[v]=t[v*2]+t[v*2+1];
   }
}
void update(int v,int tl,int tr,int pos){
   if(tl==tr)t[v]=0;
   else{
      int tm=(tl+tr)/2;
      if(pos<=tm)update(v*2,tl,tm,pos);
      else update(v*2+1,tm+1,tr,pos);
      t[v]=t[v*2]+t[v*2+1];
   }
}
long long get(int v,int tl,int tr,int l,int r){
   if(r<tl or tr<l)return 0;
   if(l<=tl && tr<=r)return t[v];
   int tm=(tl+tr)/2;
   return get(v*2,tl,tm,l,r)+get(v*2+1,tm+1,tr,l,r);
}
 
 
long long count_swaps(vector<int> s) {
    int n=s.size();
    s.insert(s.begin(),0);
    build(1,1,n);
   set <int > v1[n+1],v0[n+1];
   vector <int> used(n+1);
   for(int i=1;i<=n;i++){
      
      if(s[i]>0)v1[s[i]].insert(i);
      if(s[i]<0)v0[-s[i]].insert(i);
   }
    long long ans=0;
    for(int i=1;i<=n;i++){
       if(used[i])continue;
        if(s[i]>0){
            auto r=v0[s[i]].upper_bound(i);
            used[*r]=1;
   
            update(1,1,n,i);
            update(1,1,n,*r);
            ans+=get(1,1,n,i,*r);
            ans++;
           v0[s[i]].erase(r);
        }
        else{
            auto r=v1[-s[i]].upper_bound(i);
           used[*r]=1;
            update(1,1,n,i);
            update(1,1,n,*r);
            ans+=get(1,1,n,i,*r);
           v1[-s[i]].erase(r);
        }
       used[i]=1;
    }
    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