oj.uz

Submission #217441

# Submission time Handle Problem Language Result Execution time Memory
217441 2020-03-29T16:57:56 Z BThero Sweeping (JOI20_sweeping) C++17
100 / 100
 5142 ms 338432 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
 
#define __DBG 1
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) if (__DBG) cerr << #x << " = " << x << endl;
 
using namespace std;
//using namespace __gnu_pbds;
 
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> que;
 
const int MAXN = (int)2e6 + 5;
 
int par[MAXN * 2];
pii arr[MAXN], ans[MAXN];
bool del[MAXN];
int n, m, q;

struct DSU {
	vector<int> val;
	vector<vector<int>> comp;
	
	void init() {
		val.clear();
		comp.clear();
	}
	
	int add(int v, int label) {
		int idx = val.size();
		val.pb(v);
		comp.pb({});
		
		if (label != -1) {
			par[label] = idx;
			comp[idx].pb(label);
		}
		
		return idx;
	}
	
	int uni(int a, int b) {
		assert(a != b);
		
		if (comp[a].size() < comp[b].size()) {
			swap(a, b);
		}
		
		val[a] = max(val[a], val[b]);
		
		for (int x : comp[b]) {
			par[x] = a;
			comp[a].pb(x);
		}
		
		comp[b].clear();
		return a;
	}
} D;

struct cmp {
	bool operator()(const int &a, const int &b) {
		return D.val[a] > D.val[b];
	}
};

pii coords(int idx) {
	return mp(D.val[par[idx * 2]], D.val[par[idx * 2 + 1]]);
}
 
void rec(int x, int y, vector<que> vec) {
	if (vec.empty()) {
		return;
	}
 
	if (x + y == n) {
		for (que it : vec) {
			if (it.fi == 1) {
				ans[it.se.se] = mp(x, y);
			}
		}
		
		return;
	}
	
	int dif = n - (x + y);
	int nx = x + (dif + 1) / 2;
	int ny = y + dif / 2 + 1;
	D.init();
	priority_queue<int, vector<int>, cmp> X, Y;
	vector<que> vecR, vecU;
	
	for (que it : vec) {
		int tp = it.fi;
		
		if (tp == 1) {
			int p = it.se.fi;
			int id = it.se.se;
			
			if (arr[p].fi >= nx) {
				vecR.pb(it);
			}
			else if (arr[p].se >= ny) {
				vecU.pb(it);
			}
			else {
				ans[id] = coords(p);
			}
		}
		else if (tp == 2) {
			// H
			// y <= L: x = max(x, n - L)
			int L = it.se.fi;
			
			if (L >= ny) {
				int z = n - L;
				int ver = D.add(z, -1);
			
				while (!X.empty() && D.val[X.top()] <= z) {
					int cur = X.top();
					X.pop();
					ver = D.uni(ver, cur);
				}
				
				X.push(ver);			
				vecU.pb(it);
			}
			else {
				vector<int> rm;
				
				while (!Y.empty() && D.val[Y.top()] <= L) {
					int cur = Y.top();
					Y.pop();
				
					for (int idx : D.comp[cur]) {
						idx /= 2;
						
						if (!del[idx]) {
							arr[idx] = coords(idx);
							arr[idx].fi = n - L;
							del[idx] = 1;
							vecR.pb(mp(4, mp(idx, -1)));
						}
					}
				}
				
				vecR.pb(it);
			}
		}
		else if (tp == 3) {
			// V
			// x <= L: y = max(y, n - L)
			int L = it.se.fi;
			
			if (L >= nx) {
				int z = n - L;
				int ver = D.add(z, -1);
	
				while (!Y.empty() && D.val[Y.top()] <= z) {
					int cur = Y.top();
					Y.pop();
					ver = D.uni(ver, cur);
				}
				
				Y.push(ver);
				vecR.pb(it);
			}
			else {
				while (!X.empty() && D.val[X.top()] <= L) {
					int cur = X.top();
					X.pop();
				
					for (int idx : D.comp[cur]) {
						idx /= 2;
					
						if (!del[idx]) {
							arr[idx] = coords(idx);
							arr[idx].se = n - L;
							del[idx] = 1;
							vecU.pb(mp(4, mp(idx, -1)));
						}
					}
				}
				
				vecU.pb(it);
			}
		}
		else {
			int p = it.se.fi;
			del[p] = 0;
			
			if (arr[p].fi >= nx) {
				del[p] = 1;
				vecR.pb(it);
			}
			else if (arr[p].se >= ny) {
				del[p] = 1;
				vecU.pb(it);
			}
			else {
				X.push(D.add(arr[p].fi, 2 * p));
				Y.push(D.add(arr[p].se, 2 * p + 1));
			}
		}
	}
	
	rec(nx, y, vecR);
	rec(x, ny, vecU);
}
 
void solve() {
	scanf("%d %d %d", &n, &m, &q);
	vector<que> vec;
	
	for (int i = 1; i <= m; ++i) {
		scanf("%d %d", &arr[i].fi, &arr[i].se);
		vec.pb(mp(4, mp(i, -1)));
	}
	
	for (int i = 1; i <= q; ++i) {
		ans[i] = mp(-1, -1);
		int tp;
		scanf("%d", &tp);
		
		if (tp <= 3) {
			int p;
			scanf("%d", &p);
			vec.pb(mp(tp, mp(p, i)));
		}
		else {
			int x, y;
			scanf("%d %d", &x, &y);
			arr[++m] = mp(x, y);
			vec.pb(mp(tp, mp(m, i)));
		}
	}
	
	rec(0, 0, vec);
	
	for (int i = 1; i <= q; ++i) {
		if (ans[i] != mp(-1, -1)) {
			printf("%d %d\n", ans[i].fi, ans[i].se);
		}
	}
}
 
int main() {
	int tt = 1;
	
	while (tt--) {
		solve();
	}
 
	return 0;
}

Compilation message

sweeping.cpp: In function 'void solve()':
sweeping.cpp:223:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:227:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &arr[i].fi, &arr[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:234:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &tp);
   ~~~~~^~~~~~~~~~~
sweeping.cpp:238:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
sweeping.cpp:243:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &x, &y);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1152 KB Output is correct
2 Correct 18 ms 896 KB Output is correct
3 Correct 9 ms 1024 KB Output is correct
4 Correct 16 ms 1152 KB Output is correct
5 Correct 14 ms 1280 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 3413 ms 129132 KB Output is correct
2 Correct 3351 ms 128220 KB Output is correct
3 Correct 3273 ms 126768 KB Output is correct
4 Correct 3040 ms 189356 KB Output is correct
5 Correct 4597 ms 150584 KB Output is correct
6 Correct 4201 ms 168228 KB Output is correct
7 Correct 3262 ms 127984 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3439 ms 148808 KB Output is correct
2 Correct 3552 ms 149756 KB Output is correct
3 Correct 2719 ms 174776 KB Output is correct
4 Correct 3638 ms 274616 KB Output is correct
5 Correct 3623 ms 232876 KB Output is correct
6 Correct 3279 ms 151424 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3439 ms 148808 KB Output is correct
2 Correct 3552 ms 149756 KB Output is correct
3 Correct 2719 ms 174776 KB Output is correct
4 Correct 3638 ms 274616 KB Output is correct
5 Correct 3623 ms 232876 KB Output is correct
6 Correct 3279 ms 151424 KB Output is correct
7 Correct 3462 ms 142368 KB Output is correct
8 Correct 3465 ms 147604 KB Output is correct
9 Correct 3494 ms 138796 KB Output is correct
10 Correct 3393 ms 176516 KB Output is correct
11 Correct 4162 ms 236580 KB Output is correct
12 Correct 4563 ms 190080 KB Output is correct
13 Correct 4475 ms 302768 KB Output is correct
14 Correct 252 ms 55496 KB Output is correct
15 Correct 885 ms 114860 KB Output is correct
16 Correct 3371 ms 144432 KB Output is correct
17 Correct 3336 ms 152504 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1152 KB Output is correct
2 Correct 18 ms 896 KB Output is correct
3 Correct 9 ms 1024 KB Output is correct
4 Correct 16 ms 1152 KB Output is correct
5 Correct 14 ms 1280 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 3413 ms 129132 KB Output is correct
8 Correct 3351 ms 128220 KB Output is correct
9 Correct 3273 ms 126768 KB Output is correct
10 Correct 3040 ms 189356 KB Output is correct
11 Correct 4597 ms 150584 KB Output is correct
12 Correct 4201 ms 168228 KB Output is correct
13 Correct 3262 ms 127984 KB Output is correct
14 Correct 3439 ms 148808 KB Output is correct
15 Correct 3552 ms 149756 KB Output is correct
16 Correct 2719 ms 174776 KB Output is correct
17 Correct 3638 ms 274616 KB Output is correct
18 Correct 3623 ms 232876 KB Output is correct
19 Correct 3279 ms 151424 KB Output is correct
20 Correct 3462 ms 142368 KB Output is correct
21 Correct 3465 ms 147604 KB Output is correct
22 Correct 3494 ms 138796 KB Output is correct
23 Correct 3393 ms 176516 KB Output is correct
24 Correct 4162 ms 236580 KB Output is correct
25 Correct 4563 ms 190080 KB Output is correct
26 Correct 4475 ms 302768 KB Output is correct
27 Correct 252 ms 55496 KB Output is correct
28 Correct 885 ms 114860 KB Output is correct
29 Correct 3371 ms 144432 KB Output is correct
30 Correct 3336 ms 152504 KB Output is correct
31 Correct 3264 ms 168860 KB Output is correct
32 Correct 3431 ms 140496 KB Output is correct
33 Correct 3544 ms 117732 KB Output is correct
34 Correct 3687 ms 169644 KB Output is correct
35 Correct 3689 ms 157104 KB Output is correct
36 Correct 3300 ms 172108 KB Output is correct
37 Correct 5142 ms 300712 KB Output is correct
38 Correct 4760 ms 338432 KB Output is correct
39 Correct 4277 ms 283256 KB Output is correct
40 Correct 3343 ms 156608 KB Output is correct