Submission #226007

#	Time	Username	Problem	Language	Result	Execution time	Memory
226007		Minnakhmetov	Sweeping (JOI20_sweeping)	C++14	0 / 100	3412 ms	445224 KiB

sweeping

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

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 2e6 + 5;

struct Q {
	int t, x, y, z;
};

struct DSU {
	int val[N], a[N];
	vector<int> v[N];

	int find_set(int x) {
		return a[x] < 0 ? x : a[x];
	}

	int get_val(int x) {
		return val[find_set(x)];
	}

	void reset(int x, int y) {
		a[x] = -1;
		val[x] = y;
		v[x] = {x};
	}

	void mrg(int x, int y) {
		x = find_set(x);
		y = find_set(y);
		if (x == y)
			return;
		if (v[x].size() < v[y].size()) {
			swap(x, y);
			swap(val[x], val[y]);
		}
		for (const int &el : v[y]) {
			v[x].push_back(el);
			a[el] = x;
		}
		v[y].clear();
	}

	void set_val(int x, int y) {
		x = find_set(x);
		val[x] = y;
	}

} dsu_x, dsu_y;

pair<int, int> ans[N];
bool send_to_up[N], send_to_right[N];
vector<int> selected;

void get_not_gr_than_x(priority_queue<pair<int, int>, 
		vector<pair<int, int>>, 
		greater<pair<int, int>>> &pq, int x) {
	selected.clear();
	while (!pq.empty() && pq.top().first <= x) {
		selected.push_back(pq.top().second);
		pq.pop();
	}
}

void upd_pq(priority_queue<pair<int, int>, 
		vector<pair<int, int>>, 
		greater<pair<int, int>>> &pq, DSU &dsu, int x) {

	get_not_gr_than_x(pq, x);

	if (!selected.empty()) {
		for (const int &y : selected) {
			dsu.mrg(y, selected[0]);
		}
		dsu.set_val(selected[0], x);
		pq.push({x, dsu.find_set(selected[0])});
	}
}

priority_queue<pair<int, int>, 
		vector<pair<int, int>>, 
		greater<pair<int, int>>> pq_x, pq_y;

void solve(int offset_x, int offset_y, int n, vector<Q> qrs) {
	if (qrs.empty())
		return;

	while (!pq_x.empty())
		pq_x.pop();

	while (!pq_y.empty())
		pq_y.pop();

	// cout << n << " " << offset_x << " " << offset_y << "\n";
	// for (Q q : qrs) {
	// 	cout << q.t << " " << q.x << " " << q.y << " " << q.z << "\n";
	// }
	// cout << "\n";

	vector<Q> up_qrs, rt_qrs;

	int sq_side = (n + 1) / 2;

	for (const Q &c : qrs) {
		if (c.t == 1) {
			if (send_to_up[c.x]) {
				up_qrs.push_back(c);
			}
			else if (send_to_right[c.x]) {
				rt_qrs.push_back(c);
			}
			else {
				ans[c.y] = {dsu_x.get_val(c.x) + offset_x, 
					dsu_y.get_val(c.x) + offset_y};
			}
		}
		else if (c.t == 2) {
			if (c.x < sq_side) {
				rt_qrs.push_back(c);
				get_not_gr_than_x(pq_y, c.x);

				for (const int &gr : selected) {
					for (const int &el : dsu_y.v[gr]) {
						if (!send_to_right[el] && !send_to_up[el]) {
							Q new_q;
							new_q.t = 4;
							new_q.x = dsu_x.get_val(el);
							new_q.y = dsu_y.get_val(el);
							send_to_right[el] = true;
							new_q.x = max(new_q.x, n - c.x);
							new_q.x -= sq_side;
							new_q.z = el;
							rt_qrs.push_back(new_q);
						}
					}
				}
			}
			else {
				upd_pq(pq_x, dsu_x, n - c.x);
				up_qrs.push_back(c);
				up_qrs.back().x = c.x - sq_side;
			}
		}
		else if (c.t == 3) {
			if (c.x < sq_side) {
				up_qrs.push_back(c);
				get_not_gr_than_x(pq_x, c.x);

				for (const int &gr : selected) {
					for (const int &el : dsu_x.v[gr]) {
						if (!send_to_right[el] && !send_to_up[el]) {
							Q new_q;
							new_q.t = 4;
							new_q.x = dsu_x.get_val(el);
							new_q.y = dsu_y.get_val(el);
							send_to_up[el] = true;
							new_q.y = max(new_q.y, n - c.x);
							new_q.y -= sq_side;
							new_q.z = el;
							up_qrs.push_back(new_q);
						}
					}
				}
			}
			else {
				upd_pq(pq_y, dsu_y, n - c.x);
				rt_qrs.push_back(c);
				rt_qrs.back().x = c.x - sq_side;
			}
		}
		else {
			if (c.x > sq_side) {
				rt_qrs.push_back(c);
				rt_qrs.back().x -= sq_side;
				send_to_right[c.z] = true;
			}
			else if (c.y > sq_side) {
				up_qrs.push_back(c);
				up_qrs.back().y -= sq_side;
				send_to_up[c.z] = true;
			}
			else {
				send_to_up[c.z] = false;
				send_to_right[c.z] = false;
				dsu_x.reset(c.z, c.x);
				dsu_y.reset(c.z, c.y);
				pq_x.push({c.x, c.z});
				pq_y.push({c.y, c.z});
			}
		}
	}

	if (n != 0) {
		solve(offset_x, offset_y + sq_side, n - sq_side, up_qrs);
		solve(offset_x + sq_side, offset_y, n - sq_side, rt_qrs);
	}
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q, z = 0;
    cin >> n >> m >> q;

    vector<Q> qrs;

    for (int i = 0; i < m; i++) {
    	int x, y;
    	cin >> x >> y;
    	qrs.push_back({4, x, y, z++});
    }

    int ask_qr_ct = 0;

    for (int i = 0; i < q; i++) {
    	Q new_q;
    	cin >> new_q.t >> new_q.x;

    	if (new_q.t == 1) {
    		new_q.x--;
    		new_q.y = ask_qr_ct++;
    	}
    	else if (new_q.t == 4) {
    		cin >> new_q.y;
    		new_q.z = z++;
    	}

    	qrs.push_back(new_q);
    }

    solve(0, 0, n, qrs);

    for (int i = 0; i < ask_qr_ct; i++) {
    	cout << ans[i].first << " " << ans[i].second << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25