Submission #217441

#	Time	Username	Problem	Language	Result	Execution time	Memory
217441		BThero	Sweeping (JOI20_sweeping)	C++17	100 / 100	5142 ms	338432 KiB

sweeping

// 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 (stderr)

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 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25