oj.uz

Submission #23033

# Submission time Handle Problem Language Result Execution time Memory
23033 2017-05-02T04:42:33 Z model_code Krave (COI14_krave) C++11
100 / 100
 1093 ms 97276 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int INF = 1e+9;

struct rect {
	int x1, y1, x2, y2;
	rect(int x1 = 0, int y1 = 0, int x2 = 0, int y2 = 0):
		x1(x1), y1(y1), x2(x2), y2(y2) {}
	long long area(void) {
		return (long long)(x2 - x1) * (y2 - y1);
	}
};

bool operator < (rect A, rect B) {
	return A.x1 != B.x1 ? A.x1 < B.x1 : A.y1 < B.y1;
}

struct tournament {
	int offset;
	int from, to, y;
	vector<set<int, greater<int>>> tree;

	tournament(int size) {
		for(offset = 1; offset <= size; offset *= 2);
		tree.resize(2 * offset);
	}
	
	void _add(int t, int lo, int hi) {
		if(lo >= to || hi <= from) return;
		if(lo >= from && hi <= to) {
			tree[t].insert(y);
			return;
		}
		int mid = (lo + hi) / 2;
		_add(2 * t, lo, mid);
		_add(2 * t + 1, mid, hi);
	}

	int query(int pos, int y) {
		int ret = -INF;
		for(pos += offset; pos > 0; pos /= 2) {
			auto it = tree[pos].lower_bound(y);
			if(it == tree[pos].end()) continue;
			ret = max(ret, *it);
		}
		return ret;
	}

	void add(int l, int r, int v) {
		from = l; to = r + 1; y = v;
		_add(1, 0, offset);
	}
};

int main(void) {

	int A, B, N;
	scanf("%d%d%d", &A, &B, &N);

	tournament down(A), left(B);
	down.add(0, A, 0);
	left.add(0, B, 0);

	set<rect> rectangles;
	rectangles.insert(rect(0, 0, A, B));

	for(int i = 0; i < N; ++i) {
		int nx, ny, d; scanf("%d%d%d", &nx, &ny, &d);
		int py = down.query(nx, ny);
		int px = left.query(ny, nx);
		
		auto it = rectangles.lower_bound(rect(px, py, -1, -1));
		int x1 = it -> x1, x2 = it -> x2, y1 = it -> y1, y2 = it -> y2;
		rectangles.erase(it);

		rect A, B;
		if(d == 1) {
			A = rect(x1, y1, x2, ny);
			B = rect(x1, ny, x2, y2);
			down.add(x1, x2, ny);
		} else {
			A = rect(x1, y1, nx, y2);
			B = rect(nx, y1, x2, y2);
			left.add(y1, y2, nx);
		}
		printf("%lld %lld\n", min(A.area(), B.area()), max(A.area(), B.area()));
		rectangles.insert(A);
		rectangles.insert(B);
	}

	return 0;

}

Compilation message

krave.cpp: In function 'int main()':
krave.cpp:63:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &A, &B, &N);
                             ^
krave.cpp:73:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int nx, ny, d; scanf("%d%d%d", &nx, &ny, &d);
                                               ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2244 KB Output is correct
2 Correct 0 ms 2112 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 27052 KB Output is correct
2 Correct 9 ms 27448 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 42364 KB Output is correct
2 Correct 239 ms 53848 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 42232 KB Output is correct
2 Correct 299 ms 53980 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 42232 KB Output is correct
2 Correct 433 ms 74308 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 42628 KB Output is correct
2 Correct 499 ms 74836 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 59656 KB Output is correct
2 Correct 579 ms 78268 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 58732 KB Output is correct
2 Correct 389 ms 65200 KB Output is correct
3 Correct 386 ms 50224 KB Output is correct
4 Correct 609 ms 81568 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1093 ms 59656 KB Output is correct
2 Correct 436 ms 69424 KB Output is correct
3 Correct 369 ms 59452 KB Output is correct
4 Correct 753 ms 96880 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 60052 KB Output is correct
2 Correct 336 ms 59656 KB Output is correct
3 Correct 369 ms 65596 KB Output is correct
4 Correct 786 ms 97276 KB Output is correct