Submission #1225353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225353		edga1	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	221 ms	26732 KiB

shoes

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

int st[525000];

void add(int x, int xl, int xr, int p){
    if(xl==xr){
        if(xl==p) st[x]++;
        return;
    }
    int mid=(xl+xr)/2;
    if(p<=mid) add(x*2+1,xl,mid,p);
    else add(x*2+2,mid+1,xr,p);
    st[x]=st[x*2+1]+st[x*2+2];
    return;
}
int sum(int x, int xl, int xr, int l, int r){
    if(xl>=l && xr<=r) return st[x];
    if(xr<l || xl>r) return 0;
    int mid=(xl+xr)/2;
    return sum(x*2+1,xl,mid,l,r)+sum(x*2+2,mid+1,xr,l,r);
}

long long count_swaps(vector<int> s) {
    int n=s.size()/2;
	map<int,priority_queue<int,vector<int>,greater<int>>> pp,np;
	for(int i=0; i<2*n; i++){
        if(s[i]>0){
            pp[s[i]].push(i);
        }else{
            np[abs(s[i])].push(i);
        }
	}
	vector<int> seen(2*n,0);
	long long rez=0;
	for(int i=0; i<2*n; i++){
        if(!seen[i]){
            int pos;
            if(s[i]>0){
                pos=np[s[i]].top();
            }else{
                pos=pp[abs(s[i])].top();
            }
            np[abs(s[i])].pop();
            pp[abs(s[i])].pop();
            rez+=abs(i-pos)-1;
            rez-=sum(0,0,2*n-1,i+1,pos);
            if(s[i]>0) rez++;
            seen[pos]=1;
            add(0,0,2*n-1,pos);
        }
	}
	return rez;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15