提出 #53459424

ソースコード 拡げる

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>
/* ！！！縦のことをX、横のことをYと書いて誤読を誘う引っ掛け問題！！！ */
#define BIT_MAX 212345
int bit_table[BIT_MAX];
void bit_add(int pos, int value) {
  pos++;
  while (pos <= BIT_MAX) {
    bit_table[pos - 1] += value;
    pos += pos & (-pos);
  }
}
int bit_sum(int pos) {
  int sum = 0;
  pos++;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

/* ！！！縦のことをX、横のことをYと書いて誤読を誘う引っ掛け問題！！！ */

#define BIT_MAX 212345

int bit_table[BIT_MAX];

void bit_add(int pos, int value) {
	pos++;
	while (pos <= BIT_MAX) {
		bit_table[pos - 1] += value;
		pos += pos & (-pos);
	}
}

int bit_sum(int pos) {
	int sum = 0;
	pos++;
	while (pos > 0) {
		sum += bit_table[pos - 1];
		pos -= pos & (-pos);
	}
	return sum;
}

char syougaibutu[212345];

struct xy_s {
	int X, Y;
};

int cmp(const void* x, const void* y) {
	struct xy_s a = *(const struct xy_s*)x, b = *(const struct xy_s*)y;
	if (a.Y != b.Y) return a.Y < b.Y ? -1 : 1;
	return a.X < b.X ? -1 : a.X > b.X;
}

int H, W, M;
struct xy_s XY[212345];

int main(void) {
	int i;
	int64_t ans;
	int uekara_ikenai_mode = 0;
	int next_sgb = 0;
	if (scanf("%d%d%d", &H, &W, &M) != 3) return 1;
	for (i = 0; i < M; i++) {
		if (scanf("%d%d", &XY[i].X, &XY[i].Y) != 2) return 1;
	}
	qsort(XY, M, sizeof(*XY), cmp);
	ans = (int64_t)H * W;
	if (XY[0].Y == 1) {
		/* 最初の列に障害物 → その下全部に障害物があるとみなす */
		/* 障害物本体は、後で処理するからここでは処理しない */
		/* 障害物があるとしておけば後で引かれるから、ここでは引かない */
		for (i = XY[0].X + 1; i <= H; i++) {
			bit_add(i, 1);
			syougaibutu[i] = 1;
		}
	}
	for (i = 1; i <= W; i++) {
		if (uekara_ikenai_mode) {
			/* 上から行けないとき、左に障害物があれば行けない */
			ans -= bit_sum(H);
		}
		for (;next_sgb < M && XY[next_sgb].Y == i; next_sgb++) {
			if (XY[next_sgb].X == 1) {
				if (!uekara_ikenai_mode) ans -= bit_sum(H);
				uekara_ikenai_mode = 1;
			}
			if (!uekara_ikenai_mode && (next_sgb == 0 || XY[next_sgb].Y != XY[next_sgb - 1].Y)) {
				/* その列で最初の障害物の所には上から行けるから、カウントする */
				ans--;
				if (!syougaibutu[XY[next_sgb].X]) {
					bit_add(XY[next_sgb].X, 1);
					syougaibutu[XY[next_sgb].X] = 1;
				}
				/* 行けない場所をカウントする */
				ans -= bit_sum(H) - bit_sum(XY[next_sgb].X);
			} else {
				if (!syougaibutu[XY[next_sgb].X]) {
					/* 障害物が無ければ行けるなら、カウントする */
					ans--;
					bit_add(XY[next_sgb].X, 1);
					syougaibutu[XY[next_sgb].X] = 1;
				}
			}
		}
	}
	printf("%" PRId64 "\n", ans);
	return 0;
}

/*

右に行く → 下に行く
or
下に行く → 右に行く

(戻っても無駄)

上からも左からも行けない → 行けない

障害物をYの昇順にソート
同点 → Xの昇順にソート (Y=1 のとき、一番上の障害物を最初に持ってくるため)

注目している障害物より左の障害物の配置をセグメント木で記録
障害物があった → その下で、左に障害物がある位置には行けない

※同じYに複数障害物がある場合に注意
障害物がある → 行けない
二重カウント注意

X=1 に障害物があったら、打ち切り (1手目の移動が止まるので)
Y=1 の障害物は、一番上のやつを行ける範囲として使う

セグメント木ではなく、BITでおｋ

-----

X=1 に障害物があったら、打ち切り (1手目の移動が止まるので) ← 嘘

.#....
......

だったら、下 → 右 で2行目全部行ける

2 6 1
2 1

→ 7

「打ち切り」にはせず、「上から行けないモード」で続行
同様に、1列目に障害物がある場合も、そこで止めず、その下全部に障害物があるとして扱う

-----

「上から行けないモード」のとき、左から行けない場所には行けない

.#....
...#..
......

3 6 2
2 1
4 2

→ 10

↑誤読があったので上の自作ケースは誤り
正しくはそれぞれ

2 6 1
1 2

3 6 2
1 2
2 4

-----

.#
#.

2 2 2
1 2
2 1

→ 1

..
#.
#.

3 2 2
2 1
3 1

→ 4

..
##
..

3 2 2
2 1
2 2

→ 2

-----

最初に「上から行けないモード」にしたとき、既存の障害物分を引けてなかった
書かれているテストケースで誤答出てるのになんで見逃してるんだよバカ

*/

提出情報

ジャッジ結果