oj.uz

Submission #130488

# Submission time Handle Problem Language Result Execution time Memory
130488 2019-07-15T10:52:39 Z imyujin Dominance (CEOI08_dominance) C++14
5 / 100
 19 ms 632 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 3005

typedef long long lint;

struct QUERY {
	lint y, x1, x2, z;
} que[2 * MAXN];

char C[MAXN];
lint A[MAXN], B[MAXN], R[MAXN];
lint xs[2 * MAXN], ys[2 * MAXN];
lint s[2 * MAXN];

int main() {
	int W, H, N;

	scanf("%d%d%d", &W, &H, &N);
	for(int i = 0; i < N; i++) scanf("\n%c%lld%lld%lld", C + i, A + i, B + i, R + i);

	for(int i = 0; i < N; i++) {
		xs[i * 2] = A[i] + B[i] - R[i];
		xs[i * 2 + 1] = A[i] + B[i] + R[i] + 1;
		ys[i * 2] = A[i] - B[i] - R[i];
		ys[i * 2 + 1] = A[i] - B[i] + R[i] + 1;
		que[i * 2] = (QUERY) { A[i] - B[i] - R[i], xs[i * 2], xs[i * 2 + 1], C[i] == 'W' ? 1 : -1 };
		que[i * 2 + 1] = (QUERY) { A[i] - B[i] + R[i] + 1, xs[i * 2], xs[i * 2 + 1], C[i] == 'W' ? -1 : 1 };
	}
	sort(xs, xs + 2 * N);
	int xn = unique(xs, xs + 2 * N) - xs;
	sort(que, que + 2 * N, [&](QUERY a, QUERY b) { return a.y < b.y; } );

	lint ansp = 0ll, ansm = 0ll;
	for(int i = 0; i < 2 * N - 1; i++) {
		int xidx1 = lower_bound(xs, xs + xn, que[i].x1) - xs;
		int xidx2 = lower_bound(xs, xs + xn, que[i].x2) - xs;
		for(int j = xidx1; j < xidx2; j++) s[j] += que[i].z;
		for(int j = 0; j < xn - 1; j++) {
			if(s[j] > 0) {
				ansp += (xs[j + 1] - xs[j]) * (que[i + 1].y - que[i].y) / 2;
				if(xs[j + 1] % 2 != xs[j] % 2 && que[i + 1].y % 2 != que[i].y % 2 && xs[j] % 2 == que[i].y % 2) ansp++;
			}
			if(s[j] < 0) {
				ansm += (xs[j + 1] - xs[j]) * (que[i + 1].y - que[i].y) / 2;
				if(xs[j + 1] % 2 != xs[j] % 2 && que[i + 1].y % 2 != que[i].y % 2 && xs[j] % 2 == que[i].y % 2) ansm++;
			}
		}
	}
	printf("%lld %lld", ansp, ansm);
	return 0;
}

Compilation message

dominance.cpp: In function 'int main()':
dominance.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &W, &H, &N);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
dominance.cpp:23:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) scanf("\n%c%lld%lld%lld", C + i, A + i, B + i, R + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Incorrect 5 ms 504 KB Output isn't correct
5 Incorrect 5 ms 504 KB Output isn't correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Incorrect 4 ms 376 KB Output isn't correct
9 Incorrect 8 ms 376 KB Output isn't correct
10 Incorrect 10 ms 632 KB Output isn't correct
11 Incorrect 10 ms 632 KB Output isn't correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Incorrect 7 ms 504 KB Output isn't correct
14 Incorrect 2 ms 256 KB Output isn't correct
15 Incorrect 19 ms 504 KB Output isn't correct
16 Incorrect 10 ms 504 KB Output isn't correct
17 Incorrect 2 ms 376 KB Output isn't correct
18 Incorrect 3 ms 376 KB Output isn't correct
19 Incorrect 4 ms 380 KB Output isn't correct
20 Incorrect 4 ms 376 KB Output isn't correct