Submission #202348

#	Time	Username	Problem	Language	Result	Execution time	Memory
202348		a_player	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	203 ms	140408 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+10;

queue<int> d[2*MAXN];
bitset<2*MAXN> v;
long long ft[2*MAXN];
int N;
void update(int k,long long val){
    int x=k+1;
    while(x<=N){
        ft[x]+=val;
        x+=x&(-x);
    }
}
long long query(int k){
    int x=k+1;
    long long s=0;
    while(x>0){
        s+=ft[x];
        x-=x&(-x);
    }
    return s;
}

long long count_swaps(vector<int> s) {
     N=s.size();
    long long ans=0;
	for(int i=0;i<N;i++)d[s[i]+MAXN].push(i);
    for(int i=0;i<N;i++)update(i,1);
    for(int i=0;i<N;i++){
        if(v[i])continue;
        d[s[i]+MAXN].pop();
        int h=d[MAXN-s[i]].front();
        d[MAXN-s[i]].pop();
        v[i]=1;
        v[h]=1;
        ans+=query(h)-query(i)-1;
        update(i,1);
        update(h,-1);
        if(s[i]>s[h])ans++;
    }
    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