Submission #780726

#	Time	Username	Problem	Language	Result	Execution time	Memory
780726		1ne	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	212 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct dataa{
	long long ans = 0;
};
struct Segment_Tree{
	vector<dataa>tree;
	void init(long long n){
		tree.resize(2*n - 1);
	}
	dataa combine(dataa left,dataa right){
		dataa res;
		res.ans = left.ans + right.ans;
		return res;
	}
	long long query(long long node,long long left,long long right,long long qleft,long long qright){
		if (qright<left|| qleft > right)return 0LL;
		if (qleft<=left && qright>=right){
			return tree[node].ans;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		return query(node + 1,left,mid,qleft,qright) + query(z,mid + 1,right,qleft,qright);
	}
	void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
		if (left > uright || right < uleft) return;
		if (uleft <= left && right <=uright){
			tree[node].ans+=v;
			return;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		if (uleft<=mid){
			update(node + 1,left,mid,uleft,uright,v);
		}
		if (uright > mid){
			update(z,mid + 1,right,uleft,uright,v);
		}
		tree[node] = combine(tree[node + 1],tree[z]);
	}
};
 
long long count_swaps(std::vector<int> arr) {
	int n = (int)arr.size();
	map<int,queue<int>>index2;
  	map<int,priority_queue<int>>index;
	Segment_Tree st;
	st.init(n);
	for (int i = 0;i<n;++i){
		if (arr[i] < 0){
			index[-arr[i]].push(i);
		}
		else index2[arr[i]].push(i);
		st.update(0,0,n-1,i,i,1);
	}
	vector<pair<int,int>>brr;
	long long ans = 0;
	for (auto x:arr){
		if (x<0)continue;
		while(!index[x].empty()){
			brr.push_back({index[x].top(),index2[x].front()});
			if (brr.back().first > brr.back().second){
				swap(brr.back().first,brr.back().second);
				++ans;
			}
			index[x].pop();
			index2[x].pop();
		}
	}
	sort(brr.begin(),brr.end());
 
	for (auto x:brr){
		ans+=st.query(0,0,n - 1,x.first,x.second) - 2;
		st.update(0,0,n-1,x.first,x.first,-1);
		st.update(0,0,n-1,x.second,x.second,-1);
	}
	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