Submission #1227769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227769		colossal_pepe	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	158 ms	149936 KiB

shoes

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

using ll = long long;

struct SGT {
	int n;
	vector<ll> t, lazy;
	SGT(int _n) : n(_n) {
		t.resize(4 * n, 0), lazy.resize(4 * n, 0);
	}
	void push(int v) {
		t[2 * v] += lazy[v];
		lazy[2 * v] += lazy[v];
		t[2 * v + 1] += lazy[v];
		lazy[2 * v + 1] += lazy[v];
		lazy[v] = 0;
	}
	void update(int v, int l, int r, int L, int R) {
		if (R < l or r < L) return;
		else if (L <= l and r <= R) t[v] += 1, lazy[v] += 1;
		else {
			push(v);
			int mid = (l + r) / 2;
			update(2 * v, l, mid, L, R);
			update(2 * v + 1, mid + 1, r, L, R);
			t[v] = t[2 * v] + t[2 * v + 1];
		}
	}
	ll query(int v, int l, int r, int i) {
		if (l == r) return t[v];
		else {
			push(v);
			int mid = (l + r) / 2;
			if (i <= mid) return query(2 * v, l, mid, i);
			else return query(2 * v + 1, mid + 1, r, i);
		}
	}
	void update(int L, int R) {
		update(1, 0, n - 1, L, R);
	}
	ll query(int x) {
		return query(1, 0, n - 1, x);
	}
};

ll n;
vector<queue<ll>> l, r;

ll count_swaps(vector<int> s) {
	n = s.size();
	l.resize((n / 2) + 1), r.resize((n / 2) + 1);
	SGT sgt = SGT(n);
	ll cnt = 0;
	for (int i = 0; i < n; i++) {
		int x = abs(s[i]);
		if (s[i] < 0) {
			if (not r[x].empty()) {
				cnt += i - (r[x].front() + sgt.query(r[x].front()));
				sgt.update(r[x].front(), i);
				r[x].pop();
			} else l[x].push(i);
		} else {
			if (not l[x].empty()) {
				cnt += i - (l[x].front() + sgt.query(l[x].front())) - 1;
				sgt.update(l[x].front(), i);
				l[x].pop();
			} else r[x].push(i);
		}
	}
	return cnt;
}

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