Submission #362232

#	Time	Username	Problem	Language	Result	Execution time	Memory
362232		lohacho	Krave (COI14_krave)	C++14	100 / 100	1459 ms	56124 KiB

krave

#include <bits/stdc++.h>

using namespace std;

struct Seg{
	long long n;
	long long inf = (long long)1e9;
	vector<vector<long long>> tree;
	Seg(){}
	Seg(long long N):n(N){
		tree.resize(n * 4);
		for(long long i = 0; i < n * 4; ++i){
			tree[i] = {inf, -inf};
		}
	}
	void push(long long x, long long l, long long r, long long pl, long long pr, vector<long long> val){
		if(pr < l || pl > r) return;
		if(l >= pl && r <= pr){
			tree[x][0] = min(tree[x][0], val[0]);
			tree[x][1] = max(tree[x][1], val[1]);
			return;
		}
		long long mid = (l + r) >> 1;
		push(x * 2, l, mid, pl, pr, val), push(x * 2 + 1, mid + 1, r, pl, pr, val);
		tree[x][0] = min(tree[x * 2][0], tree[x * 2 + 1][0]);
		tree[x][1] = max(tree[x * 2][1], tree[x * 2 + 1][1]);
	}
	long long left(long long x, long long l, long long r, long long fl, long long fr, long long val){
		if(fr < l || fl > r) return inf;
		if(tree[x][0] > val || tree[x][1] < val) return inf;
		if(l == r) return l;
		long long mid = (l + r) >> 1;
		long long rv = left(x * 2, l, mid, fl, fr, val);
		if(rv != inf) return rv;
		return left(x * 2 + 1, mid + 1, r, fl, fr, val);
	}
	long long right(long long x, long long l, long long r, long long fl, long long fr, long long val){
		if(fr < l || fl > r) return -inf;
		if(tree[x][0] > val || tree[x][1] < val) return -inf;
		if(l == r) return l;
		long long mid = (l + r) >> 1;
		long long rv = right(x * 2 + 1, mid + 1, r, fl, fr, val);
		if(rv != -inf) return rv;
		return right(x * 2, l, mid, fl, fr, val);
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long h, w;
	cin >> h >> w;
	long long n;
	cin >> n;
	vector<vector<long long>> p(n, vector<long long>(3));
	vector<vector<long long>> srt(2, vector<long long>(n));
	for(long long i = 0; i < n; ++i){
		for(long long j = 0; j < 3; ++j){
			cin >> p[i][j];
		}
		srt[0][i] = p[i][0], srt[1][i] = p[i][1];
	}
	srt[0].push_back(0), srt[0].push_back(h);
	srt[1].push_back(0), srt[1].push_back(w);
	for(long long i = 0; i < 2; ++i){
		sort(srt[i].begin(), srt[i].end());
	}
	vector<vector<long long>> vv(2, vector<long long>(n + 8));
	for(long long i = 0; i < n; ++i){
		for(long long j = 0; j < 2; ++j){
			p[i][j] = lower_bound(srt[j].begin(), srt[j].end(), p[i][j]) - srt[j].begin();
			vv[j][p[i][j]] = max(vv[j][p[i][j]], p[i][j]);
			p[i][j] = vv[j][p[i][j]]++;
		}
	}
	Seg tree[2];
	tree[0] = tree[1] = Seg(n + 8);
	long long inf = (long long)1e9;
	for(long long i = 0; i < 2; ++i){
		tree[i].push(1, 0, n + 1, 0, 0, {-inf, inf});
		tree[i].push(1, 0, n + 1, (long long)srt[i].size() - 1, (long long)srt[i].size() - 1, {-inf, inf});
	}
	for(long long i = 0; i < n; ++i){
		--p[i][2];
		long long c = p[i][2];
		long long l = tree[c].right(1, 0, n + 1, 0, p[i][c] - 1, p[i][1 - c]);
		long long r = tree[c].left(1, 0, n + 1, p[i][c] + 1, (long long)srt[c].size() - 1, p[i][1 - c]);
		long long d = tree[1 - c].right(1, 0, n + 1, 0, p[i][1 - c] - 1, p[i][c]);
		long long u = tree[1 - c].left(1, 0, n + 1, p[i][1 - c] + 1, (long long)srt[1 - c].size() - 1, p[i][c]);
		long long L = srt[c][l], R = srt[c][r], D = srt[1 - c][d], U = srt[1 - c][u];
		long long v1 = abs((R - L) * (srt[1 - c][p[i][1 - c]] - D)), v2 = abs((R - L) * (U - srt[1 - c][p[i][1 - c]]));
		if(v1 > v2){
			swap(v1, v2);
		}
		cout << v1 << ' ' << v2 << '\n';
		tree[1 - c].push(1, 0, n + 1, p[i][1 - c], p[i][1 - c], {l, r});
	}
	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