Submission #217384

#	Time	Username	Problem	Language	Result	Execution time	Memory
217384		BThero	Sweeping (JOI20_sweeping)	C++17	1 / 100	18097 ms	137496 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)1e6 + 5;

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;
	set<int> S;
	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) {
				for (int idx : S) {
					arr[idx].fi = max(arr[idx].fi, n - L);
				}
				
				vecU.pb(it);
			}
			else {				
				vector<int> rm;
				
				for (int idx : S) {
					if (arr[idx].se <= L) {
						arr[idx].fi = max(arr[idx].fi, n - L);
						
						if (arr[idx].fi >= nx) {
							rm.pb(idx);
						}
					}
				}
								
				for (int idx : rm) {
					S.erase(idx);
					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) {
				for (int idx : S) {
					arr[idx].se = max(arr[idx].se, n - L);
				}
				
				vecR.pb(it);
			}
			else {				
				vector<int> rm;
				
				for (int idx : S) {
					if (arr[idx].fi <= L) {
						arr[idx].se = max(arr[idx].se, n - L);
						
						if (arr[idx].se >= ny) {
							rm.pb(idx);
						}
					}
				}
				
				for (int idx : rm) {
					S.erase(idx);
					vecU.pb(mp(4, mp(idx, -1)));
				}
				
				vecU.pb(it);
			}
		}
		else {
			int p = it.se.fi;
			
			if (arr[p].fi >= nx) {
				vecR.pb(it);
			}
			else if (arr[p].se >= ny) {
				vecU.pb(it);
			}
			else {
				S.insert(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)));
		}
	}
	
	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:153: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:157: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:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &tp);
   ~~~~~^~~~~~~~~~~
sweeping.cpp:168:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
    ~~~~~^~~~~~~~~~
sweeping.cpp:173: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: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25