Submission #219182

#	Time	Username	Problem	Language	Result	Execution time	Memory
219182		atoiz	청소 (JOI20_sweeping)	C++14	100 / 100	5137 ms	115412 KiB

sweeping

/*input
8 1 8
1 5
4 4 1
2 6
1 2
2 3
4 2 2
2 5
1 1
1 3
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <numeric>

using namespace std;

const int MAXN = 1500007, INF = 1e9 + 8;
int N, M, Q;
pair<int, int> ans[MAXN];
#define x first
#define y second

void minimize(int &x, int y) { x = (x < y ? x : y); }
void maximize(int &x, int y) { x = (x > y ? x : y); }

struct Event
{
	int type, x, id;
} events[MAXN];

struct SegmentTree
{
	int N;
	vector<int> val, lazy;
	
	void init(int _N, int x = -1)
	{
		N = _N;
		val.assign(N << 2, x);
		lazy.assign(N << 2, x);
	}

	void pushdown(int rt)
	{
		if (~lazy[rt]) {
			maximize(val[rt << 1], lazy[rt]);
			maximize(val[rt << 1 | 1], lazy[rt]);
			maximize(lazy[rt << 1], lazy[rt]);
			maximize(lazy[rt << 1 | 1], lazy[rt]);
			lazy[rt] = -1;
		}
	}

	void modify(int l, int r, int x, int rt, int lo, int hi)
	{
		if (hi < l || r < lo) return;
		if (l <= lo && hi <= r) return maximize(val[rt], x), maximize(lazy[rt], x);

		pushdown(rt);
		int md = (lo + hi) >> 1;
		modify(l, r, x, rt << 1, lo, md);
		modify(l, r, x, rt << 1 | 1, md + 1, hi);
	}
	void modify(int l, int r, int x)
	{
		modify(l, r, x, 1, 0, N - 1);
	}

	int get(int i, int rt, int lo, int hi)
	{
		if (lo == hi) return val[rt];
		pushdown(rt);
		int md = (lo + hi) >> 1;
		if (i <= md) return get(i, rt << 1, lo, md);
		else return get(i, rt << 1 | 1, md + 1, hi);
	}
	int get(int i)
	{
		return get(i, 1, 0, N - 1);
	}
} st_h, st_v;

struct DSU
{	
	int N = 0;
	vector<int> dsu, lo, hi;

	void init(int _N)
	{
		N = _N;
		dsu.resize(N), lo.resize(N), hi.resize(N);
		for (int i = 0; i < N; ++i) dsu[i] = -1, lo[i] = i, hi[i] = i + 1;
	}

	int root(int x) { return (dsu[x] < 0 ? x : dsu[x] = root(dsu[x])); }
	void join(int x, int y)
	{
		x = root(x), y = root(y);
		if (x == y) return;
		if (dsu[x] > dsu[y]) swap(x, y);
		dsu[x] += dsu[y];
		dsu[y] = x;
		minimize(lo[x], lo[y]);
		maximize(hi[x], hi[y]);
	}
	pair<int, int> get(int id) { return id = root(id), make_pair(lo[id], hi[id]); }
} dsu;

pair<int, int> cur_pos[MAXN];
vector<int> pos_x, rem, seg_h, seg_v, dusts, group;
vector<pair<int, int>> tmp_pos;
vector<vector<int>> segs_h;
void solve(int lo, int hi)
{
	if (lo == hi) return;
	int mid = (lo + hi) >> 1;
	solve(lo, mid), solve(mid + 1, hi);

	// identify dust IDs
	int from_id = INF, to_id = 0;
	for (int i = lo; i <= mid; ++i) {
		if (events[i].type == 4) {
			minimize(from_id, events[i].id);
			maximize(to_id, events[i].id);
		}
	}
	if (from_id > to_id) return;
	// cout << "\nrange " << lo << ' ' << hi << endl;

	// identify pos_x
	pos_x.clear(), pos_x.push_back(-1);
	for (int i = mid + 1; i <= hi; ++i) {
		if (events[i].type == 2 || events[i].type == 3) {
			pos_x.push_back(events[i].x);		
		}
	}
	sort(pos_x.begin(), pos_x.end()), pos_x.erase(unique(pos_x.begin(), pos_x.end()), pos_x.end());
	auto get_x = [&](int x) -> int { return int(lower_bound(pos_x.begin(), pos_x.end(), x) - pos_x.begin()); };
	int X = (int) pos_x.size();
	pos_x.push_back(N);
	// cout << "pos_x "; for (int x : pos_x) cout << x << ' '; cout << endl;

	// find segments
	rem.assign(hi - mid, -1);
	seg_h.assign(X + 1, -1), seg_v.assign(X + 1, -1);
	st_h.init(X, -1), st_v.init(X, -1);
	segs_h.assign(X + 1, vector<int>(0));
	for (int i = mid + 1; i <= hi; ++i) {
		if (events[i].type == 2) {
			int x = get_x(events[i].x);
			int p = get_x(st_h.get(x));
			if (p == x) continue;
			assert(p < x);

			if (!~seg_h[x]) {
				rem[i - (mid + 1)] = x;
				seg_h[x] = p;
				segs_h[p + 1].push_back(x);
				st_v.modify(p + 1, x, N - events[i].x);
			}
		} else if (events[i].type == 3) {
			int x = get_x(events[i].x);
			int p = get_x(N - st_v.get(x));
			if (p == x) continue;
			assert(p > x);

			if (!~seg_v[x]) {
				rem[i - (mid + 1)] = x;
				seg_v[x] = p;
				st_h.modify(x, p - 1, events[i].x);
			}
		}
	}

	// find dusts
	dusts.resize(to_id - from_id + 1);
	iota(dusts.begin(), dusts.end(), from_id);
	sort(dusts.begin(), dusts.end(), [&](int i, int j) { return cur_pos[i].x < cur_pos[j].x; });

	// sort dusts into dsu groups
	group.assign(to_id - from_id + 1, -1);
	st_v.init(X + 1, 0);
	dsu.init(X);
	vector<int>::iterator dust_it = dusts.begin();
	for (int x = 0; x <= X; ++x) {
		for (int x1 : segs_h[x]) {
			// cout << "horizontal " << x1 << endl;
			st_v.modify(x1 + 1, X, x1);
		}

		for (; dust_it != dusts.end() && cur_pos[*dust_it].x <= pos_x[x]; ++dust_it) {
			int id = *dust_it;
			group[id - from_id] = st_v.get(get_x(N - cur_pos[id].y));
			// cout << "group " << id << ": " << group[id - from_id] << " | " << N - cur_pos[id].y << endl;
		}

		if (~seg_v[x]) {
			// cout << "vertical " << x << ": " << seg_v[x] << endl;
			st_v.modify(x + 1, seg_v[x], x);
		}
	}
	assert(dust_it == dusts.end());

	// calc final pos
	auto get_pos = [&](pair<int, int> pnt, int g) -> pair<int, int> {
		pair<int, int> lim = dsu.get(g);
		maximize(pnt.first, pos_x[lim.first] + 1);
		minimize(pnt.first, pos_x[lim.second]);
		maximize(pnt.second, N - pos_x[lim.second]);
		minimize(pnt.second, N - pos_x[lim.first] - 1);
		return pnt;
	};
	tmp_pos.resize(to_id - from_id + 1);
	for (int i = from_id; i <= to_id; ++i) {
		tmp_pos[i - from_id] = cur_pos[i];
		// cout << cur_pos[i].x << ' ' << cur_pos[i].y << " -> ";
		cur_pos[i] = get_pos(tmp_pos[i - from_id], group[i - from_id]);
		// cout << cur_pos[i].x << ' ' << cur_pos[i].y;
		// auto x = dsu.get(group[i - from_id]); cout << " = " << pos_x[x.x] << ' ' << pos_x[x.y] << endl;
	}

	for (int i = hi; i >= mid + 1; --i) {
		if (events[i].type == 1 && events[i].x >= from_id && events[i].x <= to_id) {
			int dust_id = events[i].x;
			// cout << "ans " << events[i].id << ": " << dust_id << " _ " << tmp_pos[dust_id - from_id].x << ' ' << tmp_pos[dust_id - from_id].y << " -> ";
			cout << flush;
			ans[events[i].id] = get_pos(tmp_pos[dust_id - from_id], group[dust_id - from_id]);
			// cout << ans[events[i].id].x << ' ' << ans[events[i].id].y;
			// auto x = dsu.get(group[dust_id - from_id]); cout << " = " << pos_x[x.x] << ' ' << pos_x[x.y] << endl;
		} else if (~rem[i - (mid + 1)]) {
			int x = rem[i - (mid + 1)];
			// cout << "rem " << i << ": " << x << endl;
			dsu.join(x - 1, x);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> Q;
	int num_events = 0, num_dusts = 0, num_questions = 0;
	for (int i = 0; i < M; ++i) {
		auto &cur = events[++num_events];
		cur.type = 4;
		cur.id = ++num_dusts;
		cin >> cur_pos[cur.id].first >> cur_pos[cur.id].second;
	}

	for (int i = 0; i < Q; ++i) {
		auto &cur = events[++num_events];
		cin >> cur.type;
		if (cur.type == 1) {
			cin >> cur.x;
			cur.id = ++num_questions;
		} else if (cur.type == 2) {
			cin >> cur.x;
			cur.x = N - cur.x - 1;
		} else if (cur.type == 3) {
			cin >> cur.x;
		} else {
			cur.id = ++num_dusts;
			cin >> cur_pos[cur.id].first >> cur_pos[cur.id].second;
		}
	}

	solve(1, num_events);
	for (int i = 1; i <= num_questions; ++i) {
		cout << ans[i].first << ' ' << ans[i].second << '\n';
	}
}

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