RiseOJ – 파이에는 파이

설명

베시와 엘시는 각각 $$N$$ 개의 파이를 구웠다 ( $1 \leq N \leq 10^5$ ). $$2N$$ 개의 파이 각각에는 베시가 매기는 맛 점수와 (다를 수도 있는) 엘시가 매기는 맛 점수가 있다.

베시는 자신의 파이 하나를 엘시에게 줄까 생각 중이다. 엘시는 베시에게 파이를 받으면, 자신의 파이 하나를 베시에게 주어야 한다는 의무감을 느낄 것이다. 인색해 보이지도 과시하는 것처럼 보이지도 않기 위해, 엘시는 (엘시가 보기에) 자신이 받은 파이보다 맛 점수가 낮지 않으면서도 $$D$$ ( $0 \leq D \leq 10^9$ )를 넘게 더 맛있지는 않은 파이를 고르려 할 것이다. 그런 파이가 없을 수도 있는데, 그 경우 엘시는 가명을 쓰고 일본으로 스스로 망명할 것이다.

엘시가 답례로 베시에게 파이를 주면, 베시도 마찬가지로 (베시가 보기에) 엘시가 방금 준 파이보다 맛 점수가 낮지 않으면서 $$D$$ 를 넘게 더 맛있지는 않은 파이를 엘시에게 주려 할 것이다. 이것이 불가능하면 베시도 스스로 망명할 것이다. 가능하다면 고른 파이를 엘시에게 준다. 이 과정은 어느 한 소가 망명하는 불행한 결말을 맞거나, 어느 한 소가 자신이 맛 점수 $$0$$ 으로 평가하는 파이를 받을 때까지 계속되는데, 후자의 경우 선물 교환이 끝나고 두 소 모두 행복해진다.

한 번 선물한 파이는 다시 선물할 수 없으며, 어느 소도 자신이 받은 파이를 되돌려 줄 수 없다는 점에 유의한다.

베시가 엘시에게 줄 첫 선물로 고를 수 있는 $$N$$ 개의 파이 각각에 대해, 두 소가 행복해질 때까지 그 교환에서 선물될 수 있는 파이의 최소 개수를 구하라.

Problem credits: Dhruv Rohatgi

제약

Problem credits: Dhruv Rohatgi

입력 형식

첫째 줄에 두 정수 $$N$$ 과 $$D$$ 가 주어진다.

다음 $$2N$$ 개의 줄에 공백으로 구분된 두 정수가 주어지는데, 각각 그 파이에 대해 베시가 매긴 점수와 엘시가 매긴 점수를 의미한다.

앞의 $$N$$ 개의 줄은 베시의 파이에 대한 것이고, 나머지 $$N$$ 개의 줄은 엘시의 파이에 대한 것이다.

모든 맛 점수는 $$[0,10^9]$$ 범위임이 보장된다.

출력 형식

출력은 $$N$$ 개의 줄로 이루어져야 한다. $$i$$ 번째 줄에는 베시의 $$i$$ 번째 파이로 시작하는 행복한 선물 교환에서 선물될 수 있는 파이의 최소 개수를 나타내는 정수 하나를 출력한다. 파이 $$i$$ 로 시작하는 어떤 선물 교환도 행복하지 않다면, $$i$$ 번째 줄에는 대신 정수 $$-1$$ 을 출력한다.

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:

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

예제 1

입력

출력

3
1

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > December > Gold

올림피아드 > USACO > 2017-2018 > December > Gold

태그

JudgeUSACO

파이에는 파이

평가 및 의견

풀이 제출