提出 #53650598

ソースコード 拡げる

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 H, W, C, Q;
struct query_s {
  int target;
  int time;
  int color;
};
/* targetの昇順 → timeの降順 */
int cmp_target(const void* x, const void* y) {
  struct query_s a = *(const struct query_s*)x, b = *(const struct query_s*)y;
  if (a.target != b.target) return a.target < b.target ? -1 : 1;
  return a.time > b.time ? -1 : a.time < b.time;
}
int row_query_count = 0, col_query_count = 0;
struct query_s row_queries[312345], col_queries[312345];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int H, W, C, Q;

struct query_s {
	int target;
	int time;
	int color;
};

/* targetの昇順 → timeの降順 */
int cmp_target(const void* x, const void* y) {
	struct query_s a = *(const struct query_s*)x, b = *(const struct query_s*)y;
	if (a.target != b.target) return a.target < b.target ? -1 : 1;
	return a.time > b.time ? -1 : a.time < b.time;
}

int row_query_count = 0, col_query_count = 0;
struct query_s row_queries[312345], col_queries[312345];

struct iro_s {
	int time;
	int color;
};

/* time の昇順 */
int cmp_time(const void* x, const void* y) {
	struct iro_s a = *(const struct iro_s*)x, b = *(const struct iro_s*)y;
	return a.time < b.time ? -1 : a.time > b.time;
}

int row_iro_count = 0, col_iro_count = 0;
struct iro_s row_iro[312345], col_iro[312345];

uint64_t ans[312345];

int main(void) {
	int i;
	if (scanf("%d%d%d%d", &H, &W, &C, &Q) != 4) return 1;
	for (i = 0; i < Q; i++) {
		int t, n, c;
		if (scanf("%d%d%d", &t, &n, &c) != 3) return 1;
		if (t == 1) {
			row_queries[row_query_count].target = n;
			row_queries[row_query_count].time = i;
			row_queries[row_query_count].color = c;
			row_query_count++;
		} else if (t == 2) {
			col_queries[col_query_count].target = n;
			col_queries[col_query_count].time = i;
			col_queries[col_query_count].color = c;
			col_query_count++;
		}
	}
	/* 各行/列ごとに最新のクエリを取り出す */
	qsort(row_queries, row_query_count, sizeof(*row_queries), cmp_target);
	qsort(col_queries, col_query_count, sizeof(*col_queries), cmp_target);
	for (i = 0; i < row_query_count; i++) {
		if (i == 0 || row_queries[i].target != row_queries[i - 1].target) {
			row_iro[row_iro_count].time = row_queries[i].time;
			row_iro[row_iro_count].color = row_queries[i].color;
			row_iro_count++;
		}
	}
	for (i = 0; i < col_query_count; i++) {
		if (i == 0 || col_queries[i].target != col_queries[i - 1].target) {
			col_iro[col_iro_count].time = col_queries[i].time;
			col_iro[col_iro_count].color = col_queries[i].color;
			col_iro_count++;
		}
	}
	qsort(row_iro, row_iro_count, sizeof(*row_iro), cmp_time);
	qsort(col_iro, col_iro_count, sizeof(*col_iro), cmp_time);
	/* 各行について、色の数を加算する。ただし、上書きされているところは除く */
	for (i = 0; i < row_iro_count; i++) {
		int delta = W;
		if (row_iro[i].time < col_iro[col_iro_count - 1].time) {
			/* 上書きされているところがある */
			if (row_iro[i].time < col_iro[0].time) {
				/* 全部上書き */
				delta -= col_iro_count;
			} else {
				int le = 0, g = col_iro_count - 1;
				while (le + 1 < g) {
					int m = le + (g - le) / 2;
					if (row_iro[i].time < col_iro[m].time) g = m; else le - m;
				}
				delta -= col_iro_count - g;
			}
		}
		ans[row_iro[i].color] += delta;
	}
	for (i = 0; i < col_iro_count; i++) {
		int delta = H;
		if (col_iro[i].time < row_iro[col_iro_count - 1].time) {
			/* 上書きされているところがある */
			if (col_iro[i].time < row_iro[0].time) {
				/* 全部上書き */
				delta -= row_iro_count;
			} else {
				int le = 0, g = row_iro_count - 1;
				while (le + 1 < g) {
					int m = le + (g - le) / 2;
					if (col_iro[i].time < row_iro[m].time) g = m; else le - m;
				}
				delta -= row_iro_count - g;
			}
		}
		ans[col_iro[i].color] += delta;
	}
	/* 答えを出力する */
	for (i = 1; i <= C; i++) {
		printf(" %" PRIu64 + (i == 1), ans[i]);
	}
	putchar('\n');
	return 0;
}

提出情報

ジャッジ結果