Submission #73944881

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>
#include <inttypes.h>
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (a > b) - (a < b);
}
int N, X, Y;
char C[16];
int A[16], B[16];
#define RECT_MAX 65536
struct rect_s {
  int l, r, u, d;
};
int nrect;
struct rect_s rects[RECT_MAX];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int N, X, Y;
char C[16];
int A[16], B[16];

#define RECT_MAX 65536

struct rect_s {
	int l, r, u, d;
};

int nrect;
struct rect_s rects[RECT_MAX];

int nx;
int xlist[RECT_MAX * 2];
int ny;
int ylist[RECT_MAX * 2];

void za(int zal[], int* nza) {
	int num = *nza, i;
	qsort(zal, *nza, sizeof(*zal), cmp);
	*nza = 1;
	for (i = 1; i < num; i++) {
		if (zal[*nza - 1] != zal[i]) zal[(*nza)++] = zal[i];
	}
}

int zaq(const int zal[], int nza, int query) {
	int l = 0, r = nza - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (zal[m] == query) return m;
		else if (zal[m] < query) l = m + 1;
		else r = m - 1;
	}
	printf("ERROR: %d not found\n", query);
	exit(72);
}

struct event_s {
	int isin;
	int coord;
	int id;
};

int cmp_event(const void* x, const void* y) {
	struct event_s a = *(const struct event_s*)x, b = *(const struct event_s*)y;
	/* 座標の昇順 */
	if (a.coord != b.coord) return (a.coord > b.coord) - (a.coord < b.coord);
	/* 同じ座標なら、消えるのを先 */
	if (a.isin && !b.isin) return 1;
	if (!a.isin && b.isin) return -1;
	/* 引き分け */
	return 0;
}

int event_count[RECT_MAX * 2];
struct event_s* events[RECT_MAX * 2];

void add_event(int idx, struct event_s event) {
	events[idx] = realloc(events[idx], sizeof(*events[idx]) * (event_count[idx] + 1));
	if (events[idx] == NULL) exit(2);
	events[idx][event_count[idx]++] = event;
}

int edge_count[RECT_MAX];
int* edges[RECT_MAX];

void add_edge(int f, int t) {
	edges[f] = realloc(edges[f], sizeof(*edges[f]) * (edge_count[f] + 1));
	if (edges[f] == NULL) exit(2);
	edges[f][edge_count[f]++] = t;
}

void events_to_edge(struct event_s events[], int num) {
	int cur_ids[2], nid = 0;
	int i;
	qsort(events, num, sizeof(*events), cmp_event);
	for (i = 0; i < num; i++) {
		if (events[i].isin) {
			if (nid >= 2) {
				puts("ERROR: too many overlaps");
				exit(72);
			}
			cur_ids[nid++] = events[i].id;
			if (nid == 2) {
				add_edge(cur_ids[0], cur_ids[1]);
				add_edge(cur_ids[1], cur_ids[0]);
			}
		} else {
			if (nid == 1) {
				if (cur_ids[0] == events[i].id) {
					nid--;
				} else {
					printf(
						"ERROR: edge to remove mismatch (exists: %d, removing: %d)\n",
							cur_ids[0], events[i].id
					);
					exit(72);
				}
			} else if (nid == 2) {
				if (cur_ids[0] == events[i].id) {
					cur_ids[0] = cur_ids[1];
					nid--;
				} else if (cur_ids[1] == events[i].id) {
					nid--;
				} else {
					printf(
						"ERROR: edge to remove mismatch (exists: %d and %d, removing: %d)\n",
							cur_ids[0], cur_ids[1], events[i].id
					);
					exit(72);
				}
			} else {
				printf("ERROR: invalid nid = %d\n", nid);
				exit(72);
			}
		}
	}
}

int ans_count;
uint64_t ans[RECT_MAX];

int cmp_uint64(const void* x, const void* y) {
	uint64_t a = *(const uint64_t*)x, b = *(const uint64_t*)y;
	return (a > b) - (a < b);
}

char visited[RECT_MAX];

uint64_t dfs(int node) {
	uint64_t res = 0;
	int i;
	if (visited[node]) return 0;
	visited[node] = 1;
	for (i = 0; i < edge_count[node]; i++) {
		res += dfs(edges[node][i]);
	}
	return res + (uint64_t)(rects[node].r - rects[node].l) * (rects[node].d - rects[node].u);
}

int main(void) {
	int i;
	if (scanf("%d%d%d", &N, &X, &Y) != 3) return 1;
	for (i = 0; i < N; i++) {
		char Cbuf[4];
		if (scanf("%3s%d%d", Cbuf, &A[i], &B[i]) != 3) return 0;
		C[i] = *Cbuf;
	}
	rects[0] = (struct rect_s){ 0, X, 0, Y };
	nrect = 1;
	for (i = 0; i < N; i++) {
		int new_nrect = nrect;
		int j;
		for (j = 0; j < nrect; j++) {
			if (C[i] == 'X') {
				if (rects[j].r <= A[i]) {
					rects[j].u -= B[i];
					rects[j].d -= B[i];
				} else if (A[i] <= rects[j].l) {
					rects[j].u += B[i];
					rects[j].d += B[i];
				} else {
					rects[new_nrect++] = (struct rect_s){
						A[i], rects[j].r, rects[j].u + B[i], rects[j].d + B[i]
					};
					rects[j].r = A[i];
					rects[j].u -= B[i];
					rects[j].d -= B[i];
				}
			} else if (C[i] == 'Y') {
				if (rects[j].d <= A[i]) {
					rects[j].l -= B[i];
					rects[j].r -= B[i];
				} else if (A[i] <= rects[j].u) {
					rects[j].l += B[i];
					rects[j].r += B[i];
				} else {
					rects[new_nrect++] = (struct rect_s){
						rects[j].l + B[i], rects[j].r + B[i], A[i], rects[j].d
					};
					rects[j].d = A[i];
					rects[j].l -= B[i];
					rects[j].r -= B[i];
				}
			}
		}
		nrect = new_nrect;
	}

	for (i = 0; i < nrect; i++) {
		xlist[i * 2] = rects[i].l;
		xlist[i * 2 + 1] = rects[i].r;
		ylist[i * 2] = rects[i].u;
		ylist[i * 2 + 1] = rects[i].d;
	}
	nx = nrect * 2;
	ny = nrect * 2;
	za(xlist, &nx);
	za(ylist, &ny);

	for (i = 0; i < nrect; i++) {
		int lid = zaq(xlist, nx, rects[i].l);
		int rid = zaq(xlist, nx, rects[i].r);
		add_event(lid, (struct event_s){ 1, rects[i].u, i });
		add_event(lid, (struct event_s){ 0, rects[i].d, i });
		add_event(rid, (struct event_s){ 1, rects[i].u, i });
		add_event(rid, (struct event_s){ 0, rects[i].d, i });
	}
	for (i = 0; i < nx; i++) {
		events_to_edge(events[i], event_count[i]);
		free(events[i]);
		events[i] = NULL;
		event_count[i] = 0;
	}
	for (i = 0; i < nrect; i++) {
		int uid = zaq(ylist, ny, rects[i].u);
		int did = zaq(ylist, ny, rects[i].d);
		add_event(uid, (struct event_s){ 1, rects[i].l, i });
		add_event(uid, (struct event_s){ 0, rects[i].r, i });
		add_event(did, (struct event_s){ 1, rects[i].l, i });
		add_event(did, (struct event_s){ 0, rects[i].r, i });
	}
	for (i = 0; i < ny; i++) {
		events_to_edge(events[i], event_count[i]);
	}

	for (i = 0; i < nrect; i++) {
		if (!visited[i]) {
			ans[ans_count++] = dfs(i);
		}
	}
	qsort(ans, ans_count, sizeof(*ans), cmp_uint64);
	printf("%d\n", ans_count);
	for (i = 0; i < ans_count; i++) {
		printf(" %" PRIu64 + !i, ans[i]);
	}
	putchar('\n');

	return 0;
}

/*

長方形をまとめて管理する
それぞれの辺の位置について、高々2本の辺しか重ならない

*/

Submission Info

Judge Result