RiseOJ – 음매 입자

설명

COWVID-19 유행 기간 동안 보호를 위해 격리된 농부 존의 소들은 지루함을 달랠 새로운 방법을 생각해 냈다. 바로 고급 물리학을 공부하는 것이다! 실제로 소들은 새로운 아원자 입자를 발견하는 데 성공했고, 이 입자에 "음매 입자"라는 이름을 붙였다.

소들은 현재 $$N$$ 개의 음매 입자( $1 \leq N \leq 10^5$ )를 이용한 실험을 진행 중이다. 입자 $$i$$ 는 $-10^9 \ldots 10^9$ 범위(양 끝 포함)의 두 정수 $$x_i$$ 와 $$y_i$$ 로 표현되는 "스핀"을 가진다. 때때로 두 음매 입자가 상호작용한다. 스핀이 $$(x_i, y_i)$$ 와 $$(x_j, y_j)$$ 인 입자들 사이의 상호작용은 $x_i \leq x_j$ 이고 $y_i \leq y_j$ 일 때만 일어날 수 있다. 이 조건에서, 두 입자 중 정확히 하나가 사라질 수 있다(다른 입자에게는 아무 일도 일어나지 않는다). 어느 시점에서든 많아야 하나의 상호작용만 일어난다.

소들은 임의의 상호작용 순서 이후 남을 수 있는 음매 입자의 최소 개수를 알고 싶다.

문제 제공: Dhruv Rohatgi

제약

배점

테스트 케이스 3-6은 $N\le 1000$ 을 만족한다.
테스트 케이스 7-12는 추가 제약이 없다.

문제 제공: Dhruv Rohatgi

입력 형식

첫째 줄에 음매 입자의 초기 개수인 정수 $$N$$ 이 하나 주어진다. 다음 $$N$$ 개의 줄 각각에 입자 하나의 스핀을 나타내는, 공백으로 구분된 두 정수가 주어진다. 모든 입자의 스핀은 서로 다르다.

출력 형식

임의의 상호작용 순서 이후 남을 수 있는 음매 입자의 최소 개수인 정수 하나를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 moop.in · 출력을 쓸 파일 moop.out

예제 1

입력

출력

설명

One possible sequence of interactions:

Particles 1 and 4 interact, particle 1 disappears.
Particles 2 and 4 interact, particle 4 disappears.
Particles 2 and 3 interact, particle 3 disappears.

Only particle 2 remains.

예제 2

입력

출력

설명

Particle 3 cannot interact with either of the other two particles, so it must
remain. At least one of particles 1 and 2 must also remain.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Silver

올림피아드 > USACO > 2019-2020 > US Open > Silver

태그

JudgeUSACO

음매 입자

평가 및 의견

풀이 제출