oj.uz

Submission #309414

# Submission time Handle Problem Language Result Execution time Memory
309414 2020-10-03T13:38:38 Z shivensinha4 Krave (COI14_krave) C++17
100 / 100
 1122 ms 80412 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) {
			//cout << a << " " << b << endl;
			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) / 2;
			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) / 2;
			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);
		//cout << cl << " " << cr << " " << cd << " " << cu << endl;
		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 30 ms 38396 KB Output is correct
2 Correct 32 ms 38852 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 43524 KB Output is correct
2 Correct 157 ms 32120 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 43668 KB Output is correct
2 Correct 186 ms 36600 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 43512 KB Output is correct
2 Correct 210 ms 41208 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 52216 KB Output is correct
2 Correct 443 ms 55672 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1109 ms 67452 KB Output is correct
2 Correct 503 ms 64248 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 66552 KB Output is correct
2 Correct 447 ms 76036 KB Output is correct
3 Correct 194 ms 28536 KB Output is correct
4 Correct 548 ms 68344 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1122 ms 67840 KB Output is correct
2 Correct 501 ms 80412 KB Output is correct
3 Correct 215 ms 36476 KB Output is correct
4 Correct 572 ms 72568 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1073 ms 67704 KB Output is correct
2 Correct 390 ms 68472 KB Output is correct
3 Correct 224 ms 45820 KB Output is correct
4 Correct 626 ms 76612 KB Output is correct