Submission #1248019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248019		kaiboy	Tram (CEOI13_tram)	C++20	100 / 100	114 ms	16444 KiB

tram

#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

const int   N = 150000;
const int   M = 30000;
const int INF = 0x3f3f3f3f;

bool used[N][2];
int ii[M], jj[M], n;
set<int> ii_, qij;
set<pair<int, int>> pp;

int dist(int i0, int j0, int i1, int j1) {
	return i0 == i1 ? 2 : i1 - i0 << 1 ^ j0 != j1;
}

int dist_(int i, int j) {
	if (used[i][j ^ 1])
		return 2;
	int ans = INF;
	int i_ = *prev(ii_.lower_bound(i));
	if (i_ >= 0)
		for (int j_ = 0; j_ < 2; j_++)
			if (used[i_][j_])
				ans = min(ans, dist(i_, j_, i, j));
	i_ = *ii_.upper_bound(i);
	if (i_ < n)
		for (int j_ = 0; j_ < 2; j_++)
			if (used[i_][j_])
				ans = min(ans, dist(i, j, i_, j_));
	return ans;
}

int calc(int l, int r) {
	int il, ir;
	if (l == -1)
		il = ir = 0;
	else if (r == n)
		il = ir = n - 1;
	else
		il = (l + r) / 2, ir = (l + r + 1) / 2;
	int i_ = -1, j_ = -1;
	for (int i = il; i <= ir; i++)
		for (int j = 0; j < 2; j++)
			if (i_ == -1 || dist_(i_, j_) < dist_(i, j))
				i_ = i, j_ = j;
	return i_ << 1 ^ j_;
}

void add(int l, int r) {
	if (r - l < 2)
		return;
	int ij = calc(l, r), i = ij / 2, j = ij % 2;
	pp.insert({ -dist_(i, j), ij });
}

void remove(int l, int r) {
	if (r - l < 2)
		return;
	int ij = calc(l, r), i = ij / 2, j = ij % 2;
	pp.erase({ -dist_(i, j), ij });
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int q; cin >> n >> q;
	ii_.insert(-1), ii_.insert(n);
	for (int ij = 0; ij < n << 1; ij++)
		qij.insert(ij);
	add(-1, n);
	for (int h = 0; h < q; h++) {
		char c; cin >> c;
		if (c == 'E') {
			int ij = *qij.begin(), i = ij >> 1, j = ij & 1;
			if (!pp.empty()) {
				auto dij = *pp.begin();
				if (!used[i][j ^ 1] || -dij.first > 2) {
					pp.erase(dij), ij = dij.second, i = ij >> 1, j = ij & 1;
					used[ii[h] = i][jj[h] = j] = true;
					ii_.insert(i);
					qij.erase(ij);
					int l = *prev(ii_.lower_bound(i));
					int r = *ii_.upper_bound(i);
					add(l, i);
					add(i, r);
					cout << i + 1 << ' ' << j + 1 << '\n';
					continue;
				}
			}
			used[ii[h] = i][jj[h] = j] = true;
			qij.erase(ij);
			auto it = ii_.lower_bound(i);
			int l = *prev(it), r = *next(it);
			remove(l, i);
			remove(i, r);
			add(l, i);
			add(i, r);
			cout << i + 1 << ' ' << j + 1 << '\n';
		} else {
			int g; cin >> g, g--;
			int i = ii[g], j = jj[g], ij = i << 1 ^ j;
			auto it = ii_.lower_bound(i);
			int l = *prev(it), r = *next(it);
			if (!used[i][j ^ 1]) {
				remove(l, i);
				remove(i, r);
				used[i][j] = false;
				ii_.erase(i);
				qij.insert(ij);
				add(l, r);
			} else {
				remove(l, i);
				remove(i, r);
				used[i][j] = false;
				qij.insert(ij);
				add(l, i);
				add(i, r);
			}
		}
	}
	return 0;
}

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