Submission #435348

#	Time	Username	Problem	Language	Result	Execution time	Memory
435348		Supersonic	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	137 ms	15644 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define SIZE 262144
int tree[SIZE*2];
int sum(int a,int b){
	a+=SIZE;b+=SIZE;int s=0;
	while(a<=b){
		if(a%2==1)s+=tree[a++];
		if(b%2==0)s+=tree[b--];
		a/=2;b/=2;
	}
	return s;
}
void add(int a,int b){
	a+=SIZE;tree[a]+=b;
	for(a/=2;a>=1;a/=2){
		tree[a]=tree[2*a]+tree[2*a+1];
	}
}
long long count_swaps(std::vector<int> s) {
	vector<int> l[100005];vector<int> r[100005];int n=s.size();
	for(int i=0;i<n;i++){
		if(s[i]<0)l[-s[i]].push_back(i);
		else r[s[i]].push_back(i);
		add(i,1);
	}
	for(int i=0;i<100005;i++){sort(l[i].rbegin(),l[i].rend());sort(r[i].rbegin(),r[i].rend());}
	long long t=0;
	for(int i=0;i<n;i++){
		//cerr<<r[-s[i]].empty()<<endl;
		if(s[i]==SIZE)continue;
		if(s[i]<0){
			if(r[-s[i]].empty()){cerr<<i<<endl;exit(1);}
			int k;int z=SIZE;while(z==SIZE||k==i){k=r[-s[i]].back();r[-s[i]].pop_back();z=s[k];}
			//cerr<<i+1<<' '<<k-1<<endl;
			t+=sum(i+1,k-1);add(k,-1);s[i]=SIZE;s[k]=SIZE;
		}
		else {
			if(l[s[i]].empty()){cerr<<i<<endl;exit(1);}
			int k;int z=SIZE;while(z==SIZE||k==i){k=l[s[i]].back();l[s[i]].pop_back();z=s[k];}
			//cerr<<i<<' '<<k-1<<endl;
			t+=sum(i,k-1);add(k,-1);s[i]=SIZE;s[k]=SIZE;
		}
	}
	return t;
}
/*int main(){
	int n;cin>>n;while(n--){int a,b;cin>>a>>b;add(a,b);}cin>>n;while(n--){int a,b;cin>>a>>b;cout<<sum(a,b)<<endl;}
}*/

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