Submission #1225395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225395		toast12	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	105 ms	15900 KiB

shoes

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

#define lc 2*v
#define rc 2*v+1
#define tm (tl+tr)/2

struct lazy_segtree {
	vector<int> tree;
	lazy_segtree(int sz) {
		tree.resize(4*sz);
		build(1, 0, sz-1);
	}
	void build(int v, int tl, int tr) {
		if (tl == tr) {
			tree[v] = tl;
			return;
		}
		build(lc, tl, tm);
		build(rc, tm+1, tr);
	}
	void pushdown(int v, int tl, int tr) {
		if (tl == tr) return;
		tree[lc] += tree[v];
		tree[rc] += tree[v];
		tree[v] = 0;
	}
	void update(int v, int tl, int tr, int l, int r, int add) {
		if (tl > r || tr < l) return;
		if (tl >= l && tr <= r) {
			tree[v] += add;
			return;
		}
		pushdown(v, tl, tr);
		update(lc, tl, tm, l, r, add);
		update(rc, tm+1, tr, l, r, add);
	}
	int query(int v, int tl, int tr, int pos) {
		pushdown(v, tl, tr);
		if (tl == tr) return tree[v];
		if (pos <= tm) return query(lc, tl, tm, pos);
		else return query(rc, tm+1, tr, pos);
	}
};

long long count_swaps(vector<int> s) {
	int n = s.size();
	long long ans = 0;
	vector<bool> done(n+1);
	vector<vector<vector<int>>> pos(2, vector<vector<int>>((n/2)+1));
	for (int i = 0; i < n; i++) {
		if (s[i] > 0) pos[0][s[i]].push_back(i);
		else pos[1][-s[i]].push_back(i);
	}
	for (int i = 1; i <= n/2; i++) {
		reverse(pos[0][i].begin(), pos[0][i].end());
		reverse(pos[1][i].begin(), pos[1][i].end());
	}
	lazy_segtree stree(n);
	for (int i = 0; i < n; i++) {
		if (done[i]) continue;
		int idx = stree.query(1, 0, n-1, i);
		int z = 0;
		if (s[i] > 0) z = 1;
		int temp = pos[z][abs(s[i])].back();
		int j = stree.query(1, 0, n-1, temp);
		done[temp] = true;
		pos[z][abs(s[i])].pop_back();
		pos[1-z][abs(s[i])].pop_back();
		done[i] = true;
		ans += j-idx-1;
		if (s[i] > 0) ans++;
		stree.update(1, 0, n-1, 0, temp-1, 1);
	}
	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