Submission #1047303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047303		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	288 ms	550376 KiB

shoes

#include "shoes.h"

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

const int lim=1e5+100;

struct{
	int tree[lim];
	void update(int p,int val){
		p++;
		while(p<lim){
			tree[p]+=val;
			p+=p&-p;
		}
	}
	int query(int p){
		p++;
		int ans=0;
		while(p){
			ans+=tree[p];
			p-=p&-p;
		}
		return ans;
	}
	int query(int l,int r){
		if(r<l)return 0;
		return query(r)-query(l-1);
	}
}fw;

long long count_swaps(std::vector<int> s) {
	int ans=0;
	int n=s.size();
	deque<int>left[n],right[n];
	for(int i=0;i<n;i++){
		if(s[i]<0){
			if(right[-s[i]].size()){
				int ind=right[-s[i]].front();
				right[-s[i]].pop_front();
				int k=fw.query(ind+1,i);
				ans+=k+i-ind;
				fw.update(i+1,-1);
				fw.update(ind,1);
			}else{
				left[-s[i]].push_back(i);
			}
		}else{
			if(left[s[i]].size()){
				int ind=left[s[i]].front();
				left[s[i]].pop_front();
				int k=fw.query(ind+1,i);
				ans+=k+i-ind-1;
				fw.update(i+1,-1);
				fw.update(ind+1,1);
			}else{
				right[s[i]].push_back(i);
			}
		}
		//cerr<<ans<<"\n";
	}
	return ans;
}

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