oj.uz

Submission #217428

# Submission time Handle Problem Language Result Execution time Memory
217428 2020-03-29T15:37:39 Z BThero Sweeping (JOI20_sweeping) C++17
1 / 100
 18000 ms 220496 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)1e6 + 5;

struct DSU {
	int par[MAXN], sz[MAXN];
	
	DSU() {}
	
	void init(int n) {
		for (int i = 1; i <= n; ++i) {
			par[i] = i;
			sz[i] = 1;
		}
	}
	
	int get(int x) {
		if (x == par[x]) {
			return x;
		}
		
		return par[x] = get(par[x]);
	}
	
	int uni(int a, int b) {
		if (a == 0) {
			return b;
		}
		
		if (b == 0) {
			return a;
		}
	
		a = get(a);
		b = get(b);
		
		if (a == b) {
			return a;
		}
		
		if (sz[a] < sz[b]) {
			swap(a, b);
		}
		
		par[b] = a;
		sz[a] += sz[b];
		return a;
	}
} DX, DY;

bool del[MAXN];
pii arr[MAXN], ans[MAXN];
int n, m, q;

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;
	map<int, vector<int>> 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] = arr[p];
			}
		}
		else if (tp == 2) {
			// H
			// y <= L: x = max(x, n - L)
			int L = it.se.fi;
			
			if (L >= ny) {
				vector<int> tot;
			
				while (!X.empty() && X.begin() -> fi <= n - L) {
					for (int idx : X.begin() -> se) {
						if (!del[idx]) {
							tot.pb(idx);
						}
					}
					
					X.erase(X.begin());
				}
				
				if (!tot.empty()) {
					for (int idx : tot) {
						arr[idx].fi = n - L;
					}
				
					X.insert(mp(n - L, tot));
				}
				
				vecU.pb(it);
			}
			else {
				vector<int> rm;
				
				while (!Y.empty() && Y.begin() -> fi <= L) {
					for (int idx : Y.begin() -> se) {
						if (!del[idx]) {
							rm.pb(idx);
						}
					}
					
					Y.erase(Y.begin());
				}
				
				for (int idx : rm) {
					del[idx] = 1;
					arr[idx].fi = max(arr[idx].fi, n - L);
					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) {
				vector<int> tot;
			
				while (!Y.empty() && Y.begin() -> fi <= n - L) {
					for (int idx : Y.begin() -> se) {
						if (!del[idx]) {
							tot.pb(idx);
						}
					}
					
					Y.erase(Y.begin());
				}
				
				if (!tot.empty()) {
					for (int idx : tot) {
						arr[idx].se = n - L;
					}
				
					Y.insert(mp(n - L, tot));
				}
				
				vecR.pb(it);
			}
			else {
				vector<int> rm;
				
				while (!X.empty() && X.begin() -> fi <= L) {
					for (int idx : X.begin() -> se) {
						if (!del[idx]) {
							rm.pb(idx);
						}
					}
					
					X.erase(X.begin());
				}
				
				for (int idx : rm) {
					del[idx] = 1;
					arr[idx].se = max(arr[idx].se, n - L);
					vecU.pb(mp(4, mp(idx, -1)));
				}
				
				vecU.pb(it);
			}
		}
		else {
			int p = it.se.fi;
			del[p] = 0;
			
			if (arr[p].fi < x || arr[p].se < y) {
				continue;
			}
			
			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[arr[p].fi].pb(p);
				Y[arr[p].se].pb(p);
			}
		}
	}
	
	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)));
		}
	}
	
	DX.init(m);
	DY.init(m);
	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:242: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:246: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:253:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &tp);
   ~~~~~^~~~~~~~~~~
sweeping.cpp:257:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
sweeping.cpp:262: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 17 ms 1024 KB Output is correct
2 Correct 14 ms 768 KB Output is correct
3 Correct 10 ms 1408 KB Output is correct
4 Correct 15 ms 1136 KB Output is correct
5 Correct 14 ms 1148 KB Output is correct
6 Correct 7 ms 768 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3132 ms 117600 KB Output is correct
2 Correct 3064 ms 119856 KB Output is correct
3 Correct 3086 ms 120248 KB Output is correct
4 Correct 3228 ms 220496 KB Output is correct
5 Execution timed out 18079 ms 117372 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2495 ms 136828 KB Output is correct
2 Correct 2389 ms 137692 KB Output is correct
3 Correct 2368 ms 167348 KB Output is correct
4 Execution timed out 18103 ms 122924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2495 ms 136828 KB Output is correct
2 Correct 2389 ms 137692 KB Output is correct
3 Correct 2368 ms 167348 KB Output is correct
4 Execution timed out 18103 ms 122924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1024 KB Output is correct
2 Correct 14 ms 768 KB Output is correct
3 Correct 10 ms 1408 KB Output is correct
4 Correct 15 ms 1136 KB Output is correct
5 Correct 14 ms 1148 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 3132 ms 117600 KB Output is correct
8 Correct 3064 ms 119856 KB Output is correct
9 Correct 3086 ms 120248 KB Output is correct
10 Correct 3228 ms 220496 KB Output is correct
11 Execution timed out 18079 ms 117372 KB Time limit exceeded
12 Halted 0 ms 0 KB -