Submission #638122

#	Time	Username	Problem	Language	Result	Execution time	Memory
638122		JJAnawat	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	63 ms	19688 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;

bool chk[200005];
vector<int> pl[200005],pr[200005];
int fw[200005];

void up(int x,int v){
    for(int i=x;i<200005;i+=i&-i)
        fw[i]+=v;
}

long long qr(int x){
    long long sum=0;
    for(int i=x;i>0;i-=i&-i)
        sum+=fw[i];
    return sum;
}

long long count_swaps(vector<int> s) {
    int n=s.size();
    for(int i=n-1;i>=0;i--){
        if(s[i]>0)
            pr[s[i]].push_back(i);
        else
            pl[-s[i]].push_back(i);
    }
    long long ans=0;
    for(int i=0;i<n;i++){
        if(chk[i])
            continue;
        int sz=abs(s[i]);
        if(s[i]>0){
            int pos=pl[sz].back();
            chk[pos]=chk[i]=1;
            pl[sz].pop_back();
            pr[sz].pop_back();
            ans+=pos-i-(qr(pos)-qr(i));
            up(pos,1);
        }
        else{
            int pos=pr[sz].back();
            chk[pos]=chk[i]=1;
            pl[sz].pop_back();
            pr[sz].pop_back();
            ans+=pos-i-1-(qr(pos)-qr(i));
            up(pos,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