oj.uz

Submission #217384

# Submission time Handle Problem Language Result Execution time Memory
217384 2020-03-29T13:46:35 Z BThero Sweeping (JOI20_sweeping) C++17
1 / 100
 18000 ms 137496 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;

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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1024 KB Output is correct
2 Correct 13 ms 664 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 15 ms 1064 KB Output is correct
5 Correct 13 ms 1080 KB Output is correct
6 Correct 7 ms 804 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2666 ms 128260 KB Output is correct
2 Correct 2678 ms 111348 KB Output is correct
3 Correct 2720 ms 113200 KB Output is correct
4 Execution timed out 18075 ms 66688 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2762 ms 134948 KB Output is correct
2 Correct 2797 ms 137496 KB Output is correct
3 Execution timed out 18097 ms 71468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2762 ms 134948 KB Output is correct
2 Correct 2797 ms 137496 KB Output is correct
3 Execution timed out 18097 ms 71468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1024 KB Output is correct
2 Correct 13 ms 664 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 15 ms 1064 KB Output is correct
5 Correct 13 ms 1080 KB Output is correct
6 Correct 7 ms 804 KB Output is correct
7 Correct 2666 ms 128260 KB Output is correct
8 Correct 2678 ms 111348 KB Output is correct
9 Correct 2720 ms 113200 KB Output is correct
10 Execution timed out 18075 ms 66688 KB Time limit exceeded
11 Halted 0 ms 0 KB -