레이팅 미적용농부 존의 목초지는 정사각형 "칸"들로 이루어진 큰 2차원 격자(거대한 체스판을 떠올려 보자)로 볼 수 있다. 처음에 목초지는 비어 있다.
농부 존은 목초지에 소 \(N\)마리(\(1\le N\le 10^5\))를 한 마리씩 추가할 것이다. \(i\)번째 소는 다른 모든 소가 차지한 칸과 다른 칸 \((x_i,y_i)\)(\(0\le x_i,y_i\le 1000\))를 차지한다.
어떤 소가 가로 또는 세로로 정확히 세 마리의 다른 소와 인접해 있으면 그 소는 "편안하다"고 한다. 농부 존은 농장의 편안한 소의 수를 세는 데 관심이 있다. \(1 \ldots N\) 범위의 각 \(i\)에 대해, \(i\)번째 소가 목초지에 추가된 후 편안한 소의 총수를 출력하시오.
문제 제공: Benjamin Qi
배점
- 테스트 케이스 1-4는 \(N\le 400\)을 만족한다.
- 테스트 케이스 5-12에는 추가 제약이 없다.
문제 제공: Benjamin Qi
첫째 줄에 정수 \(N\)이 주어진다. 다음 \(N\)개의 줄 각각에는 공백으로 구분된 두 정수가 주어지며, 이는 소가 있는 칸의 \((x,y)\) 좌표를 나타낸다. 이 칸들이 모두 서로 다름이 보장된다.
출력의 \(i\)번째 줄에는 처음 \(i\)마리의 소가 목초지에 추가된 후 편안한 소의 총수를 출력한다.
8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 20
0
0
1
0
0
1
2After the first four cows are added, the cow at \((1,1)\) is comfortable.
After the first seven cows are added, the cow at \((2,1)\) is comfortable.
After the first eight cows are added, the cows at \((2,1)\) and \((2,2)\) are
comfortable.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > February > Bronze