Submission #144057

#	Time	Username	Problem	Language	Result	Execution time	Memory
144057		Lyestria	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	438 ms	273080 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mn=2e5+10;
queue<int>pos[mn],neg[mn];
int par[mn];
int bit[mn];
void up(int a,int b){for(;a<mn;a+=a&-a)bit[a]+=b;}
int qu(int a){int b=0;for(;a;a-=a&-a)b+=bit[a];return b;}
bool done[mn];
long long count_swaps(std::vector<int> s) {
	int n=s.size();
	ll ans=0;
	int i;
	for(i=0;i<n;i++){
        if(s[i]>0){
            pos[s[i]].push(i);
        }
        else{
            neg[-s[i]].push(i);
        }
	}
	for(i=1;i<mn;i++)up(i,1);
	int ac=1;
	for(i=0;i<n;i++){
        if(done[i])continue;
        int p;
        if(s[i]>0){
            ans++;
            p=neg[s[i]].front();
        }
        else{
            p=pos[-s[i]].front();
        }
        ans+=qu(p)-ac;
        done[p]=1;
        up(i+1,1);
        up(p,-1);
        neg[abs(s[i])].pop();
        pos[abs(s[i])].pop();
        ac+=2;
	}
	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