Submission #309414

#	Time	Username	Problem	Language	Result	Execution time	Memory
309414		shivensinha4	Krave (COI14_krave)	C++17	100 / 100	1122 ms	80412 KiB

krave

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12