Submission #737124

#	Time	Username	Problem	Language	Result	Execution time	Memory
737124		NeroZein	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	300 ms	274028 KiB

shoes

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

const int N = 200005;

int seg[N << 1]; 
void upd (int nd, int l, int r, int p) {
	if (l == r) {
		seg[nd] ^= 1; 
		return;
	}
	int mid = (l + r) >> 1;
	int rs = nd + ((mid - l + 1) << 1);
	if (p <= mid) {
		upd(nd + 1, l, mid, p);		
	} else {
		upd(rs, mid + 1, r, p); 
	}
	seg[nd] = seg[nd + 1] + seg[rs]; 
}
void upd (int p) {
	return upd(0, 0, N - 1, p); 
}

int qry (int nd, int l, int r, int s, int e) {
	if (l >= s && r <= e) {
		return seg[nd];
	}
	int mid = (l + r) >> 1;
	int rs = nd + ((mid - l + 1) << 1);
	if (mid >= e) {
		return qry(nd + 1, l, mid, s, e); 
	} else {
		if (mid < s) {
			return qry(rs, mid + 1, r, s, e);
		} else {
			return qry(nd + 1, l, mid, s, e) + qry(rs, mid + 1, r, s, e);
		}
	}
}
int qry (int l, int r) {
	return qry(0, 0, N - 1, l, r); 
}

long long count_swaps(std::vector<int> s) {
	int n = (int) s.size(); 
	vector<queue<int>> v[2];
	v[0].resize(n); 
	v[1].resize(n);  
	long long ans = 0; 
	for (int i = 0; i < n; ++i) {
		bool neg = s[i] < 0; 
		if (neg) s[i] = -s[i];
		s[i]--; 
		if (neg) {
			if (v[0][s[i]].size()) {
				int match = v[0][s[i]].front();
				upd(match); 
				ans += i - match - qry(match + 1, i); 
				v[0][s[i]].pop(); 
			} else {
				upd(i); 
				v[1][s[i]].push(i); 
			}
		} else {
			if (v[1][s[i]].size()) {
				int match = v[1][s[i]].front(); 
				upd(match); 
				ans += i - match - 1 - qry(match + 1, i); 
				v[1][s[i]].pop(); 
			} else {
				upd(i); 
				v[0][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