oj.uz

Submission #309418

# Submission time Handle Problem Language Result Execution time Memory
309418 2020-10-03T13:40:10 Z shivensinha4 Krave (COI14_krave) C++17
100 / 100
 1110 ms 79736 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef set<int> Node;
#define endl '\n'

class SegmentTree {
	private:
		vector<Node> tree; int n;
		
		int merge(int a, int b, bool larger) {
			if (a > b) swap(a, b);
			if (a == -1) return b;
			return larger ? a : b;
		}
		
		void update(int i, int j, int val, int l, int r, int p) {
			if (l > j or r < i) return;
			if (l >= i and r <= j) {
				tree[p].insert(val);
				return;
			}
			
			int mid = (l + r) >> 1;
			int c1 = 2*p+1, c2 = 2*p+2;
			update(i, j, val, l, mid, c1); update(i, j, val, mid+1, r, c2);
		}
		
		int query(int i, int j, bool larger, int l, int r, int p) {
			if (l > i or r < i) return -1;
			
			int ans = -1;
			if (tree[p].size()) {
				if (larger) {
					auto pt = tree[p].upper_bound(j);
					if (pt != tree[p].end()) ans = *pt;
				} else {
					auto pt = tree[p].upper_bound(j);
					if (pt != tree[p].begin()) ans = *(--pt);
				}
			}
			
			if (l == r) return ans;
			
			int mid = (l + r) >> 1;
			int c1 = 2*p+1, c2 = 2*p+2;
			return merge(ans, merge(query(i, j, larger, l, mid, c1), query(i, j, larger, mid+1, r, c2), larger), larger);
		}
	
	public: 
		SegmentTree(int N) {
			n = N;
			tree.resize(4*n);
		}
		
		ll query(int i, int j, bool larger) {
			return query(i, j, larger, 0, n-1, 0);
		}
		
		void update(int i, int j, int val) {
			update(i, j, val, 0, n-1, 0);
		}
};





int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int A, B; cin >> A >> B;
	SegmentTree hor(A+1), ver(B+1);
	hor.update(0, A, 0); hor.update(0, A, B);
	ver.update(0, B, 0); ver.update(0, B, A);
	
	int n; cin >> n;
	for_(i, 0, n) {
		ll x, y, d; cin >> x >> y >> d;
		ll cr = ver.query(y, x, true), cl = ver.query(y, x, false), cu = hor.query(x, y, true), cd = hor.query(x, y, false);
		ll a, b;
		if (d == 1) {
			a = (cu-y) * (cr-cl), b = (y-cd) * (cr-cl);
			hor.update(cl, cr, y);
		}
		else {
			a = (x-cl) * (cu-cd), b = (cr-x) * (cu-cd);
			ver.update(cd, cu, x);
		}
		cout << min(a, b) << " " << max(a, b) << endl;
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 38284 KB Output is correct
2 Correct 32 ms 38752 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 42996 KB Output is correct
2 Correct 159 ms 31224 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 43000 KB Output is correct
2 Correct 180 ms 35704 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 43000 KB Output is correct
2 Correct 207 ms 40056 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 51704 KB Output is correct
2 Correct 424 ms 54776 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 66172 KB Output is correct
2 Correct 491 ms 63228 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1050 ms 65360 KB Output is correct
2 Correct 452 ms 75640 KB Output is correct
3 Correct 197 ms 27512 KB Output is correct
4 Correct 535 ms 67244 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 66296 KB Output is correct
2 Correct 494 ms 79736 KB Output is correct
3 Correct 213 ms 35192 KB Output is correct
4 Correct 569 ms 71544 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 66488 KB Output is correct
2 Correct 371 ms 67960 KB Output is correct
3 Correct 227 ms 44664 KB Output is correct
4 Correct 606 ms 75384 KB Output is correct