Submission #299905

#	Time	Username	Problem	Language	Result	Execution time	Memory
299905		nhdtxdy	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	193 ms	23928 KiB

shoes

#include <bits/stdc++.h>
#define ll long long
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define Size(v) (int)v.size()
#define pb push_back
#define eb emplace_back
using namespace std;

struct SegTree {
	int n;
	vector<int> st;
	SegTree(int n) {
		this->n = n;
		st.resize(4 * n + 1, 0);
	}
	void update(int pos, int val, int id, int u, int v) {
		if (pos < u || v < pos) return;
		if (u == v) {
			st[id] = val;
			return;
		}
		int mid = (u + v) / 2;
		update(pos, val, id * 2, u, mid);
		update(pos, val, id * 2 + 1, mid + 1, v);	
		st[id] = st[id * 2] + st[id * 2 + 1];
	}
	int query(int l, int r, int id, int u, int v) {
		if (l > r) return 0;
		if (r < u || v < l) return 0;
		if (l <= u && v <= r) return st[id];
		int mid = (u + v) / 2;
		int lv = query(l, r, id * 2, u, mid);
		int rv = query(l, r, id * 2 + 1, mid + 1, v);
		return (lv + rv);
	}
	void update(int pos, int val) {
		update(pos, val, 1, 1, n);
	}	
	int query(int l, int r) {
		return query(l, r, 1, 1, n);
	}
};

const int nax = 4e5 + 5;
// map<int, int> pos, curr;
int curr[nax + 2];
vector<int> appear[nax + 2];
int mp[nax + 2];
bool solved[nax + 2], used[nax + 2];

int64_t count_swaps(vector<int> a) {
	int n = Size(a);
	// cerr << "here1\n";
	SegTree st(n);
	// cerr << "?\n";
	for (int i = 1; i <= n; ++i) st.update(i, 1);
	// cerr << "here3\n";
	for (int i = 0; i < n; ++i) {
		int idx = a[i];
		if (a[i] < 0) idx = nax + a[i];
		appear[idx].pb(i + 1);
	}
	for (int i = 0; i < n; ++i) {
		if (used[i + 1]) continue;
		used[i + 1] = true;
		int idx = -a[i];
		if (idx < 0) idx = nax + idx;
		mp[i + 1] = appear[idx][curr[idx]];
		int idxa = a[i];
		if (idxa < 0) idxa = nax + idxa;
		++curr[idxa], ++curr[idx];
		used[mp[i + 1]] = true;
	}
	// cerr << "here2\n";
	int64_t res = 0;
	for (int i = 1; i <= n; ++i) {
		if (solved[i]) continue;
		solved[i] = true;
		int d = mp[i];
		solved[d] = true;
		if (a[i - 1] < 0) {
			res += st.query(i + 1, d - 1);
		}
		else res += st.query(i, d - 1);
		st.update(d, 0);
	}
	return res;
}

void test() {
	int n; cin >> n;
	vector<int> a;
	for (int i = 0; i < n; ++i) {
		int c; cin >> c;
		a.pb(c);
	}
	cout << count_swaps(a) << '\n';
}

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