oj.uz

Submission #225239

# Submission time Handle Problem Language Result Execution time Memory
225239 2020-04-19T19:33:16 Z Minnakhmetov Sweeping (JOI20_sweeping) C++14
64 / 100
 8276 ms 466824 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 267384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4808 ms 466824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3994 ms 420260 KB Output is correct
2 Correct 3696 ms 412740 KB Output is correct
3 Correct 2771 ms 411208 KB Output is correct
4 Correct 3498 ms 413244 KB Output is correct
5 Correct 3327 ms 413676 KB Output is correct
6 Correct 3468 ms 412400 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3994 ms 420260 KB Output is correct
2 Correct 3696 ms 412740 KB Output is correct
3 Correct 2771 ms 411208 KB Output is correct
4 Correct 3498 ms 413244 KB Output is correct
5 Correct 3327 ms 413676 KB Output is correct
6 Correct 3468 ms 412400 KB Output is correct
7 Correct 6281 ms 413820 KB Output is correct
8 Correct 6384 ms 413564 KB Output is correct
9 Correct 6387 ms 413388 KB Output is correct
10 Correct 4480 ms 412848 KB Output is correct
11 Correct 8276 ms 413384 KB Output is correct
12 Correct 6758 ms 414720 KB Output is correct
13 Correct 6275 ms 415236 KB Output is correct
14 Correct 312 ms 279768 KB Output is correct
15 Correct 1449 ms 392860 KB Output is correct
16 Correct 6176 ms 413728 KB Output is correct
17 Correct 6316 ms 413052 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 267384 KB Output isn't correct
2 Halted 0 ms 0 KB -