oj.uz

Submission #225238

# Submission time Handle Problem Language Result Execution time Memory
225238 2020-04-19T19:13:07 Z Minnakhmetov Sweeping (JOI20_sweeping) C++14
64 / 100
 17173 ms 927832 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;
set<pair<int, int>> st[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 (!st[v].empty() &&
			st[v].begin()->first <= y) {
			int x = st[v].begin()->second;
			st[v].erase(st[v].begin());

			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) {
	st[v].insert(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);

    		// if (q.x == 2) {
    		// 	cout << l << " " << r << "\n";
    		// }

    		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));
    	}

    	// prt(rt);
    	// cout << "\n";
    }

    return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12588 ms 927200 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 5785 ms 921464 KB Output is correct
2 Correct 5767 ms 925624 KB Output is correct
3 Correct 4521 ms 923192 KB Output is correct
4 Correct 5031 ms 925688 KB Output is correct
5 Correct 5277 ms 926324 KB Output is correct
6 Correct 5544 ms 925384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5785 ms 921464 KB Output is correct
2 Correct 5767 ms 925624 KB Output is correct
3 Correct 4521 ms 923192 KB Output is correct
4 Correct 5031 ms 925688 KB Output is correct
5 Correct 5277 ms 926324 KB Output is correct
6 Correct 5544 ms 925384 KB Output is correct
7 Correct 13178 ms 926204 KB Output is correct
8 Correct 12511 ms 926216 KB Output is correct
9 Correct 12611 ms 926320 KB Output is correct
10 Correct 11927 ms 924976 KB Output is correct
11 Correct 17173 ms 925936 KB Output is correct
12 Correct 14293 ms 927568 KB Output is correct
13 Correct 13865 ms 927832 KB Output is correct
14 Correct 373 ms 407624 KB Output is correct
15 Correct 8938 ms 852520 KB Output is correct
16 Correct 12936 ms 926372 KB Output is correct
17 Correct 12861 ms 926304 KB Output is correct

Subtask #5
0 / 25.0

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