Submission #225239

#	Time	Username	Problem	Language	Result	Execution time	Memory
225239		Minnakhmetov	Sweeping (JOI20_sweeping)	C++14	64 / 100	8276 ms	466824 KiB

sweeping

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

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

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

const int N = 2e6 + 5, INF = 1e9;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq[N * 4];
vector<pair<int, int>> pts;
vector<Q> qrs;
bool used[N];
vector<int> vx, pts_to_add;
int lc[N], rc[N], mn_x[N], mn_y[N], up_x[N], up_y[N], sz[N], anc[N], pr[N];
pair<int, int> val[N];
int cv = 1;

bool is_earlier(pair<int, int> &a, pair<int, int> &b) {
	return a.first == b.first ? a.second > b.second : a.first < b.first;
}

void get_pts_to_add(int x, int y, int v = 1, int L = 0, int R = vx.size() - 1) {
	if (L > x)
		return;
	if (R <= x) {
		while (!pq[v].empty() &&
			pq[v].top().first <= y) {
			int x = pq[v].top().second;
			pq[v].pop();

			if (!used[x]) {
				used[x] = true;
				pts_to_add.push_back(x);
			}
		}
	}
	else {
		int m = (L + R) >> 1;
		get_pts_to_add(x, y, v * 2, L, m);
		get_pts_to_add(x, y, v * 2 + 1, m + 1, R);
	}
}

void add_pt(int x, pair<int, int> y, int v = 1, int L = 0, int R = vx.size() - 1) {
	pq[v].push(y);
	if (L != R) {
		int m = (L + R) >> 1;
		if (x <= m)
			add_pt(x, y, v * 2, L, m);
		else
			add_pt(x, y, v * 2 + 1, m + 1, R);
	}
}

void push(int v) {
	if (v == 0)
		return;
	if (up_x[v]) {
		up_x[lc[v]] = up_x[v];
		up_x[rc[v]] = up_x[v];
		val[v].first = up_x[v];
		mn_x[v] = up_x[v];
		up_x[v] = 0;
	}
	if (up_y[v]) {
		up_y[lc[v]] = up_y[v];
		up_y[rc[v]] = up_y[v];
		val[v].second = up_y[v];
		mn_y[v] = up_y[v];
		up_y[v] = 0;
	}
}

void upd(int v) {
	sz[v] = sz[lc[v]] + sz[rc[v]] + 1;
	mn_x[v] = val[v].first;
	mn_y[v] = val[v].second;
	if (lc[v] != 0) {
		mn_x[v] = min(mn_x[lc[v]], mn_x[v]);
		mn_y[v] = min(mn_y[lc[v]], mn_y[v]);
	}
	if (rc[v] != 0) {
		mn_x[v] = min(mn_x[rc[v]], mn_x[v]);
		mn_y[v] = min(mn_y[rc[v]], mn_y[v]);
	}
	anc[lc[v]] = v;
	anc[rc[v]] = v;
}

pair<int, int> split(int v, pair<int, int> k) {
	if (v == 0)
		return {0, 0};
	push(v);
	push(lc[v]);
	push(rc[v]);
	if (is_earlier(val[v], k)) {
		auto p = split(rc[v], k);
		rc[v] = p.first;
		upd(v);
		anc[v] = 0;
		return {v, p.second};
	}
	auto p = split(lc[v], k);
	lc[v] = p.second;
	upd(v);
	anc[v] = 0;
	return {p.first, v};
}

int mrg(int a, int b) {
	push(a);
	push(b);
	if (a == 0) {
		upd(b);
		return b;
	}
	if (b == 0) {
		upd(a);
		return a;
	}
	if (pr[a] > pr[b]) {
		rc[a] = mrg(rc[a], b);
		upd(a);
		return a;
	}
	lc[b] = mrg(a, lc[b]);
	upd(b);
	return b;
}

int first_y_not_gr(int v, int k) {
	if (v == 0)
		return INF;

	push(v);
	push(lc[v]);
	push(rc[v]);

	if (lc[v] != 0 && mn_y[lc[v]] <= k)
		return first_y_not_gr(lc[v], k);
	if (val[v].second <= k)
		return sz[lc[v]];
	return first_y_not_gr(rc[v], k) + 1 + sz[lc[v]];
}

int last_x_not_gr(int v, int k) {
	if (v == 0)
		return -INF;
	push(v);
	push(lc[v]);
	push(rc[v]);
	if (rc[v] != 0 && mn_x[rc[v]] <= k)
		return last_x_not_gr(rc[v], k) + sz[lc[v]] + 1;
	if (val[v].first <= k)
		return sz[lc[v]];
	return last_x_not_gr(lc[v], k);
}

void asgn_x(int v, int l, int r, int x) {
	push(v);
	if (l > r)
		return;
	if (l == 0 && r == sz[v] - 1) {
		up_x[v] = x;
		push(v);
	}
	else {
		asgn_x(lc[v], l, min(r, sz[lc[v]] - 1), x);
		if (l <= sz[lc[v]] && r >= sz[lc[v]])
			val[v].first = x;
		asgn_x(rc[v], max(0, l - sz[lc[v]] - 1), r - sz[lc[v]] - 1, x);
		upd(v);
	}
}

void asgn_y(int v, int l, int r, int x) {
	push(v);
	if (l > r)
		return;
	if (l == 0 && r == sz[v] - 1) {
		up_y[v] = x;
		push(v);
	}
	else {
		asgn_y(lc[v], l, min(r, sz[lc[v]] - 1), x);
		if (l <= sz[lc[v]] && r >= sz[lc[v]])
			val[v].second = x;
		asgn_y(rc[v], max(0, l - sz[lc[v]] - 1), r - sz[lc[v]] - 1, x);
		upd(v);
	}
}

void prt(int v) {
	if (v == 0)
		return;
	push(v);
	prt(lc[v]);
	cout << val[v].first << " " << val[v].second << "\n";
	prt(rc[v]);
}

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

    int n, m, q;
    cin >> n >> m >> q;

    mt19937 rnd(time(0));

    for (int i = 1; i < N; i++) {
    	pr[i] = rnd();
    	sz[i] = 1;
    }

    for (int i = 0; i < m; i++) {
    	int x, y;
    	cin >> x >> y;
    	pts.emplace_back(x, y);
    	val[i + 1] = {x, y};
    	vx.push_back(x);
    }

    for (int i = 0; i < q; i++) {
    	int type, x, y;
    	cin >> type >> x;

    	if (type == 1) {
    		qrs.push_back({type, x - 1});
    	}
    	else if (type == 2 || type == 3) {
    		qrs.push_back({type, x});
    	}
    	else {
    		cin >> y;
			qrs.push_back({type, (int)pts.size()});
    		pts.push_back({x, y});
    		vx.push_back(x);
    		val[pts.size()] = {x, y};
    	}
    }

    sort(all(vx));
    vx.erase(unique(all(vx)), vx.end());

    for (int i = 0; i < m; i++) {
    	add_pt(lower_bound(all(vx), pts[i].first) - vx.begin(), make_pair(pts[i].second, i));
    }

    int rt = 0;

    for (const Q &q : qrs) {
    	if (q.t == 1) {
    		pair<int, int> ans = val[q.x + 1];;
    		int v = q.x + 1;
    		while (v != 0) {
    			if (up_x[v])
    				ans.first = up_x[v];
    			if (up_y[v])
    				ans.second = up_y[v];
    			v = anc[v];
    		}
    		cout << ans.first << " " << ans.second << "\n";
    	}
    	else if (q.t == 2) {
    		int l = first_y_not_gr(rt, q.x),
    			r = last_x_not_gr(rt, n - q.x);

    		asgn_x(rt, l, r, n - q.x);

    		pts_to_add.clear();
    		int b = upper_bound(all(vx), n - q.x) - vx.begin();
    		b--;
    		get_pts_to_add(b, q.x);
    		for (int i : pts_to_add) {
    			i++;
    			val[i].first = n - q.x;
    			auto p = split(rt, val[i]);
    			rt = mrg(p.first, mrg(i, p.second));
    		}
    	}
    	else if (q.t == 3) {
    		int l = first_y_not_gr(rt, n - q.x),
    			r = last_x_not_gr(rt, q.x);
    		asgn_y(rt, l, r, n - q.x);

    		pts_to_add.clear();
    		int b = upper_bound(all(vx), q.x) - vx.begin();
    		b--;
    		get_pts_to_add(b, n - q.x);
    		for (int i : pts_to_add) {
    			i++;
    			val[i].second = n - q.x;
    			auto p = split(rt, val[i]);
    			rt = mrg(p.first, mrg(i, p.second));
    		}
    	}
    	else {
    		add_pt(lower_bound(all(vx), pts[q.x].first) - vx.begin(), make_pair(pts[q.x].second, q.x));
    	}
    }

    return 0;
}

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