Submission #1350649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350649		ttparin_	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	69 ms	140568 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
long long a[200010];
long long idx[200010];
queue<long long> q[200010];
long long n;
long long dp[200010];
long long read(long long idx){
long long sumi=0;
 while(idx>0){
    sumi+=dp[idx];
    idx-=idx&-idx;
 }
 return sumi;
}
void update(long long idx){
 while(idx<=n){
    dp[idx]++;
    idx+=idx&-idx;
 }
}
long long count_swaps(vector<int> s) {
    long long ans=0;
    for(auto g:s){
        n++;
        if(g<0){
            g=100000-g;
            if(q[g-100000].empty()==0){
                a[q[g-100000].front()]=n;
                a[n]=q[g-100000].front();
                q[g-100000].pop();
            }
            else{
                q[g].push(n);
            }
        }
        else{
            if(q[g+100000].empty()==0){
                a[q[g+100000].front()]=n;
                a[n]=q[g+100000].front();
                q[g+100000].pop();
            }
            else{
                q[g].push(n);
            }
        }
    }
    for(long long i=1;i<=n;i++){
      if(a[i]>i){
        long long x=read(a[i]-1)-read(i);
        ans+=a[i]-i-1-x;
        if(s[i-1]>0){ans++;}
        update(i);
        update(a[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