Byteasar는 스케이트 동호회를 운영한다. 동호회 회원들은 정기적으로 모여 함께 훈련하며, 항상 동호회에서 보유한 스케이트를 사용한다.
스케이트의 사이즈는 관례적으로 1부터 n까지 번호가 매겨져 있다. 각 회원은 발 사이즈 r를 가지며, 추가로 허용 오차 d가 있다.
즉, 발 사이즈가 r인 회원은 사이즈가 r부터 r+d까지인 스케이트를 신을 수 있다. 단, 어떤 회원도 동시에 서로 다른 사이즈의 스케이트 두 짝을 신지는 않는다.
(즉, 한 사람은 같은 사이즈의 한 켤레만 신는다.)
동호회는 사이즈 1부터 n까지 각 사이즈별로 스케이트 k 켤레씩을 구비해 두었다.
시간이 지나면서 어떤 사람들은 가입하고, 기존 회원들 중 일부는 탈퇴한다.
Byteasar는 매 훈련 시점마다 모든 회원에게 적절한 사이즈의 스케이트를 충분히 제공할 수 있는지 걱정하고 있다.
처음에는 동호회에 회원이 한 명도 없다고 가정한다. Byteasar는 다음과 같은 형태의 이벤트 m개를 순서대로 제공한다 : “발 사이즈가 r인 신규 회원 x명이 가입/탈퇴했다.” 각 이벤트 직후에, Byteasar는 모든 회원에게 적절한 스케이트를 제공할 수 있는지 알고 싶어 한다. 이를 확인하는 프로그램을 작성하라.
입력
표준 입력의 첫 줄에는 네 정수 n,m,k,d가 공백으로 구분되어 주어진다.
(1≤n≤200,000, 1≤m≤500,000, 1≤k≤10^9, 0≤d<n)
다음 줄부터 mmm개의 줄에 걸쳐 이벤트가 주어진다. i(1≤i≤m)번째 이벤트는 두 정수 r_i, x_i로 주어진다.
(1≤r_i≤n−d, −10^9≤x_i≤10^9)
x_i≥0이면, 발 사이즈가 r_i인 신규 회원 x_i명이 막 가입했음을 의미한다.
x_i<0이면, 발 사이즈가 r_i인 회원 −x_i명이 막 탈퇴했음을 의미한다.
이 이벤트 열은 일관적이라고 가정해도 좋다. 즉, 가입한 적이 없는 회원이 탈퇴하는 경우는 입력으로 주어지지 않는다.
출력
표준 출력으로 총 m줄을 출력한다.
i번째 줄에는 i번째 이벤트 직후에 모든 회원에게 적절한 사이즈의 스케이트를 제공할 수 있다면 TAK(폴란드어로 “예”), 그렇지 못하다면 NIE(“아니오”)를 출력한다.
kjk9704 1년 전 1
문제
Byteasar는 스케이트 동호회를 운영한다.
동호회 회원들은 정기적으로 모여 함께 훈련하며, 항상 동호회에서 보유한 스케이트를 사용한다.
스케이트의 사이즈는 관례적으로 1부터 n까지 번호가 매겨져 있다. 각 회원은 발 사이즈 r를 가지며, 추가로 허용 오차 d가 있다.
즉, 발 사이즈가 r인 회원은 사이즈가 r부터 r+d까지인 스케이트를 신을 수 있다. 단, 어떤 회원도 동시에 서로 다른 사이즈의 스케이트 두 짝을 신지는 않는다.
(즉, 한 사람은 같은 사이즈의 한 켤레만 신는다.)
동호회는 사이즈 1부터 n까지 각 사이즈별로 스케이트 k 켤레씩을 구비해 두었다.
시간이 지나면서 어떤 사람들은 가입하고, 기존 회원들 중 일부는 탈퇴한다.
Byteasar는 매 훈련 시점마다 모든 회원에게 적절한 사이즈의 스케이트를 충분히 제공할 수 있는지 걱정하고 있다.
처음에는 동호회에 회원이 한 명도 없다고 가정한다. Byteasar는 다음과 같은 형태의 이벤트 m개를 순서대로 제공한다 : “발 사이즈가 r인 신규 회원 x명이 가입/탈퇴했다.” 각 이벤트 직후에, Byteasar는 모든 회원에게 적절한 스케이트를 제공할 수 있는지 알고 싶어 한다. 이를 확인하는 프로그램을 작성하라.
입력
표준 입력의 첫 줄에는 네 정수 n,m,k,d가 공백으로 구분되어 주어진다.
(1≤n≤200,000, 1≤m≤500,000, 1≤k≤10^9, 0≤d<n)
다음 줄부터 mmm개의 줄에 걸쳐 이벤트가 주어진다. i(1≤i≤m)번째 이벤트는 두 정수 r_i, x_i로 주어진다.
(1≤r_i≤n−d, −10^9≤x_i≤10^9)
x_i≥0이면, 발 사이즈가 r_i인 신규 회원 x_i명이 막 가입했음을 의미한다.
x_i<0이면, 발 사이즈가 r_i인 회원 −x_i명이 막 탈퇴했음을 의미한다.
이 이벤트 열은 일관적이라고 가정해도 좋다. 즉, 가입한 적이 없는 회원이 탈퇴하는 경우는 입력으로 주어지지 않는다.
출력
표준 출력으로 총 m줄을 출력한다.
i번째 줄에는 i번째 이벤트 직후에 모든 회원에게 적절한 사이즈의 스케이트를 제공할 수 있다면 TAK(폴란드어로 “예”), 그렇지 못하다면 NIE(“아니오”)를 출력한다.