Submission #72980753

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
struct event_s {
  int sx, dx, y, delta;
};
/* yの昇順、yが同じならdeltaの降順 (deltaが正のほうが先) */
int cmp(const void* x, const void* y) {
  struct event_s a = *(const struct event_s*)x, b = *(const struct event_s*)y;
  return
    ((a.y > b.y) - (a.y < b.y)) * 2 +
    ((a.delta < b.delta) - (a.delta > b.delta));
}
int n;
int a, b;
int p[5123], q[5123], r[5123], s[5123];
struct event_s events[5123 * 2];
int counts[1123456];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

struct event_s {
	int sx, dx, y, delta;
};

/* yの昇順、yが同じならdeltaの降順 (deltaが正のほうが先) */
int cmp(const void* x, const void* y) {
	struct event_s a = *(const struct event_s*)x, b = *(const struct event_s*)y;
	return
		((a.y > b.y) - (a.y < b.y)) * 2 +
		((a.delta < b.delta) - (a.delta > b.delta));
}

int n;
int a, b;
int p[5123], q[5123], r[5123], s[5123];

struct event_s events[5123 * 2];
int counts[1123456];
int counts_of_counts[5123];
int areas[5123];

int main(void) {
	int i;
	int max_sheets = 0;
	if (scanf("%d", &n) != 1) return 1;
	if (scanf("%d%d", &a, &b) != 2) return 1;
	for (i = 0; i < n; i++) {
		if (scanf("%d%d%d%d", &p[i], &q[i], &r[i], &s[i]) != 4) return 1;
		events[i * 2] = (struct event_s){ p[i], r[i], q[i], 1 };
		events[i * 2 + 1] = (struct event_s){ p[i], r[i], s[i] + 1, -1 };
	}
	events[n * 2] = (struct event_s){ 0, 0, 0, 0 };
	qsort(events, n * 2 + 1, sizeof(*events), cmp);
	for (i = 1; i <= n * 2; i++) {
		int j;
		for (j = 1; j <= max_sheets; j++) {
			areas[j] += counts_of_counts[j] * (events[i].y - events[i - 1].y);
		}
		for (j = events[i].sx; j <= events[i].dx; j++) {
			counts_of_counts[counts[j]]--;
			counts[j] += events[i].delta;
			counts_of_counts[counts[j]]++;
		}
		max_sheets += events[i].delta;
	}
	for (i = n; i > 0; i--) {
		if (areas[i] > 0) {
			printf("%d\n%d\n", i, areas[i]);
			return 0;
		}
	}
	puts("ERROR!");
	return 0;
}

Submission Info

Judge Result