oj.uz

Submission #362232

# Submission time Handle Problem Language Result Execution time Memory
362232 2021-02-02T09:01:58 Z lohacho Krave (COI14_krave) C++14
100 / 100
 1459 ms 56124 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 876 KB Output is correct
2 Correct 3 ms 876 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1393 ms 27384 KB Output is correct
2 Correct 273 ms 39288 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1373 ms 27604 KB Output is correct
2 Correct 302 ms 44816 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1427 ms 27512 KB Output is correct
2 Correct 348 ms 50476 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 27092 KB Output is correct
2 Correct 278 ms 39424 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 53784 KB Output is correct
2 Correct 320 ms 45220 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1286 ms 53692 KB Output is correct
2 Correct 179 ms 25420 KB Output is correct
3 Correct 397 ms 55740 KB Output is correct
4 Correct 344 ms 47512 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1459 ms 53692 KB Output is correct
2 Correct 195 ms 28264 KB Output is correct
3 Correct 373 ms 56124 KB Output is correct
4 Correct 359 ms 50348 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1196 ms 53692 KB Output is correct
2 Correct 156 ms 22712 KB Output is correct
3 Correct 386 ms 55996 KB Output is correct
4 Correct 385 ms 53044 KB Output is correct