Submission #1047284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047284		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	348 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();
	unordered_map<int,int>mp;
	for(int i=0;i<n;i++){
		if(mp.count(-s[i])){
			int ind=mp[-s[i]];
			mp.erase(-s[i]);
			int k=fw.query(ind+1,i);
			ans+=k;
			fw.update(i+1,-1);
			if(s[i]<0){
				ans+=i-ind;
				fw.update(ind,1);
			}else{
				ans+=i-ind-1;
				fw.update(ind+1,1);
			}
		}else{
			mp[s[i]]=i;
		}
		//cerr<<ans<<"\n";
	}
	return ans;
}

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