oj.uz

Submission #220398

# Submission time Handle Problem Language Result Execution time Memory
220398 2020-04-07T20:31:51 Z super_j6 Sweeping (JOI20_sweeping) C++14
100 / 100
 4771 ms 286840 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second

const int maxn = 3000000;
int n, m, q;
vector<pi> pt, qry;
int par[maxn], crd[maxn];
bool used[maxn];
vector<int> val;
vector<vector<int>> st;
vector<pi> ans;

void init(){
	val.clear(), st.clear();
}

int add(int x, int id){
	int nid = val.size();
	val.push_back(x);
	st.push_back({});
	if(id >= 0){
		par[id] = nid;
		st[nid].push_back(id);
	}
	return nid;
}

int unionf(int x, int y){
	if(x == y) return x;
	if(st[x].size() < st[y].size()) swap(x, y);
	val[x] = max(val[x], val[y]);
	for(int i : st[y]){
		par[i] = x;
		st[x].push_back(i);
	}
	return x;
}

pi gtpt(int x){
	return {val[par[2 * x]], val[par[2 * x + 1]]};
}

void solve(int x, int y, vector<pi> qry){
	if(qry.empty()) return;
	
	if(x + y == n){
		for(pi qr : qry){
			if(qr.f == 1) ans[qr.s] = pt[ans[qr.s].f];
		}
		return;
	}
	
	int X = x + (n - x - y) / 2 + 1, Y = n + 1 - X;
	vector<pi> qup, qrt;
	init();
	priority_queue<pi, vector<pi>, greater<pi>> xq, yq;
	for(pi qr : qry){
		 if(qr.f == 1){
		 	int i = ans[qr.s].f;
		 	if(pt[i].f >= X) qrt.push_back(qr);
		 	else if(pt[i].s >= Y) qup.push_back(qr);
		 	else{
		 		ans[qr.s] = gtpt(i);
		 	}
		 }
		 if(qr.f == 2){
		 	if(qr.s >= Y){
		 		int nx = n - qr.s;
		 		int cid = add(nx, -1);
		 		while(!xq.empty() && xq.top().f < nx){
		 			cid = unionf(cid, xq.top().s);
		 			xq.pop();
		 		}
		 		xq.push({nx, cid});
		 		qup.push_back(qr);
		 	}else{
		 		while(!yq.empty() && yq.top().f <= qr.s){
		 			for(int i : st[yq.top().s]){
		 				i /= 2;
		 				if(!used[i]){
		 					pt[i] = gtpt(i);
		 					pt[i].f = n - qr.s;
		 					qrt.push_back({4, i});
		 					used[i] = 1;
		 				}
		 			}
		 			yq.pop();
		 		}
		 		qrt.push_back(qr);
		 	}
		 }
		 if(qr.f == 3){
		 	if(qr.s >= X){
		 		int ny = n - qr.s;
		 		int cid = add(ny, -1);
		 		while(!yq.empty() && yq.top().f < ny){
		 			cid = unionf(cid, yq.top().s);
		 			yq.pop();
		 		}
		 		yq.push({ny, cid});
		 		qrt.push_back(qr);
		 	}else{
		 		while(!xq.empty() && xq.top().f <= qr.s){
		 			for(int i : st[xq.top().s]){
		 				i /= 2;
		 				if(!used[i]){
		 					pt[i] = gtpt(i);
		 					pt[i].s = n - qr.s;
		 					qup.push_back({4, i});
		 					used[i] = 1;
		 				}
		 			}
		 			xq.pop();
		 		}
		 		qup.push_back(qr);
		 	}
		 }
		 if(qr.f == 4){
		 	used[qr.s] = 0;
		 	int x = pt[qr.s].f, y = pt[qr.s].s;
		 	if(x >= X) used[qr.s] = 1, qrt.push_back(qr);
		 	else if(y >= Y) used[qr.s] = 1, qup.push_back(qr);
		 	else{
		 		int xid = add(x, 2 * qr.s);
		 		int yid = add(y, 2 * qr.s + 1);
		 		xq.push({x, xid});
		 		yq.push({y, yid});
		 	}
		 }
	}
	solve(X, y, qrt), solve(x, Y, qup);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m >> q;
	
	for(int i = 0; i < m + q; i++){
		int t;
		if(i < m) t = 4;
		else cin >> t;
		if(t == 1){
			int x;
			cin >> x;
			x--;
			qry.push_back({t, ans.size()});
			ans.push_back({x, -1});
		}else if(t < 4){
			int x;
			cin >> x;
			qry.push_back({t, x});
		}else{
			int x, y;
			cin >> x >> y;
			qry.push_back({t, pt.size()});
			pt.push_back({x, y});
		}
	}
	
	solve(0, 0, qry);
	
	for(pi i : ans) cout << i.f << " " << i.s << endl;

	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1024 KB Output is correct
2 Correct 15 ms 768 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 16 ms 1152 KB Output is correct
5 Correct 13 ms 1152 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3221 ms 99004 KB Output is correct
2 Correct 3146 ms 98856 KB Output is correct
3 Correct 3132 ms 100052 KB Output is correct
4 Correct 2565 ms 141060 KB Output is correct
5 Correct 4155 ms 120060 KB Output is correct
6 Correct 3781 ms 127764 KB Output is correct
7 Correct 3122 ms 101276 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3345 ms 109992 KB Output is correct
2 Correct 3429 ms 136472 KB Output is correct
3 Correct 2536 ms 159388 KB Output is correct
4 Correct 3336 ms 237968 KB Output is correct
5 Correct 3359 ms 198616 KB Output is correct
6 Correct 3053 ms 134408 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3345 ms 109992 KB Output is correct
2 Correct 3429 ms 136472 KB Output is correct
3 Correct 2536 ms 159388 KB Output is correct
4 Correct 3336 ms 237968 KB Output is correct
5 Correct 3359 ms 198616 KB Output is correct
6 Correct 3053 ms 134408 KB Output is correct
7 Correct 3257 ms 120124 KB Output is correct
8 Correct 3284 ms 134816 KB Output is correct
9 Correct 3423 ms 120720 KB Output is correct
10 Correct 3085 ms 155852 KB Output is correct
11 Correct 3681 ms 205912 KB Output is correct
12 Correct 4363 ms 169652 KB Output is correct
13 Correct 4224 ms 252812 KB Output is correct
14 Correct 132 ms 37076 KB Output is correct
15 Correct 737 ms 98064 KB Output is correct
16 Correct 3176 ms 128064 KB Output is correct
17 Correct 3142 ms 131352 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1024 KB Output is correct
2 Correct 15 ms 768 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 16 ms 1152 KB Output is correct
5 Correct 13 ms 1152 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 3221 ms 99004 KB Output is correct
8 Correct 3146 ms 98856 KB Output is correct
9 Correct 3132 ms 100052 KB Output is correct
10 Correct 2565 ms 141060 KB Output is correct
11 Correct 4155 ms 120060 KB Output is correct
12 Correct 3781 ms 127764 KB Output is correct
13 Correct 3122 ms 101276 KB Output is correct
14 Correct 3345 ms 109992 KB Output is correct
15 Correct 3429 ms 136472 KB Output is correct
16 Correct 2536 ms 159388 KB Output is correct
17 Correct 3336 ms 237968 KB Output is correct
18 Correct 3359 ms 198616 KB Output is correct
19 Correct 3053 ms 134408 KB Output is correct
20 Correct 3257 ms 120124 KB Output is correct
21 Correct 3284 ms 134816 KB Output is correct
22 Correct 3423 ms 120720 KB Output is correct
23 Correct 3085 ms 155852 KB Output is correct
24 Correct 3681 ms 205912 KB Output is correct
25 Correct 4363 ms 169652 KB Output is correct
26 Correct 4224 ms 252812 KB Output is correct
27 Correct 132 ms 37076 KB Output is correct
28 Correct 737 ms 98064 KB Output is correct
29 Correct 3176 ms 128064 KB Output is correct
30 Correct 3142 ms 131352 KB Output is correct
31 Correct 3010 ms 144508 KB Output is correct
32 Correct 3311 ms 129120 KB Output is correct
33 Correct 3282 ms 115172 KB Output is correct
34 Correct 3552 ms 137472 KB Output is correct
35 Correct 3576 ms 124712 KB Output is correct
36 Correct 2936 ms 153936 KB Output is correct
37 Correct 4771 ms 265876 KB Output is correct
38 Correct 4613 ms 286840 KB Output is correct
39 Correct 3916 ms 221956 KB Output is correct
40 Correct 3159 ms 136984 KB Output is correct