Submission #1215346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215346		brinton	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	124 ms	137800 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
struct BIT{
	private:
	vector<int> tree;
	int N;
	void modify(int idx,int dv,int _){
		for(int i = idx;i <= N;i+= i&-i){
			tree[i] += dv;
		}
	}
	int query(int idx,int _){
		int ans = 1;
		for(int i = idx;i >= 1;i-= i&-i){
			ans += tree[i];
		}
		return ans;
	}
	public:
	void modify(int idx,int dv){
		modify(idx+1,dv,-1);
	}
	int query(int idx){
		return query(idx+1,-1);
	}
	BIT(int iN){
		N = iN;
		tree.resize(N+1);
		for(int i = 0;i < N;i++){
			modify(i,1);
		}
	}
};
long long count_swaps(vector<int> s) {
	int N = s.size()/2;

	vector<queue<int>> left(N+1);
	vector<queue<int>> right(N+1);
	long long ans = 0;
	BIT bit(2*N);
	for(int i = 0;i < 2*N;i++){
		if(s[i] < 0){
			// left
			if(!right[-s[i]].empty()){
				// move right to left
				auto prev = right[-s[i]].front();
				right[-s[i]].pop();
				// cout << prev << " " << i << ":" << bit.query(i)-bit.query(prev) << endl;
				ans += bit.query(i)-bit.query(prev);
				bit.modify(prev,1);
				bit.modify(i,-1);
			}else{
				left[-s[i]].push(i);
			}
		}else{
			// right
			if(!left[s[i]].empty()){
				// move left to right
				auto prev = left[s[i]].front();
				left[s[i]].pop();
				ans += bit.query(i)-bit.query(prev)-1;
				bit.modify(prev,1);
				bit.modify(i,-1);
			}else{
				right[s[i]].push(i);
				
			}
		}
	}
	return ans;
}

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