Problem : 133 - 溜冰鞋

Problem Statistics

Solved Member: 6　　Submission: 21　　User Tried: 6

Statement:

你開了一家溜冰俱樂部，俱樂部裡有 n 種大小的溜冰鞋，大小由 1 標號到 n。每個人不見得要穿符合自己腳大小的溜冰鞋，事實上，如果一個人腳的大小為 r，則他可以穿大小 r 到 r+d 的鞋子。並且，這家俱樂部擁有 1 到 n 的溜冰鞋各 k 雙。

現在溜冰鞋俱樂部有 m 件事情依序發生，每件事情有可能是來了/走了 x 位腳大小為 r 號的會員。你想知道，每件事情發生之後存不存在一組分配溜冰鞋的方案使得每個人都有一雙溜冰鞋可以穿。

Input:Output:

第 1 行有四個整數 n,m,k,d(1 ≤ n ≤ 200000, 1 ≤ m ≤ 500000, 1 ≤ k ≤ 10^9, 0 ≤ d < n)，四個整數之間以一個空白分隔，分別代表溜冰鞋的種類、事情有幾件、每種溜冰鞋有幾雙、以及每個人適合的大小範圍。

接下來的 m 行每行有 2 個數字 ri,xi (1 ≤ ri ≤ n, -10^9 ≤ xi ≤ 10^9)，兩個數字以空格分隔。
如果 0 ≤ xi，代表來了 xi 位腳大小 ri 的人，否則代表走了 -xi 位腳大小 ri 的人。

請注意再第一筆詢問之前，俱樂部沒有任何的人。並且在任何的時間保證進來的人 >= 出去的人。

對於每一筆詢問，若存在一種分配溜冰鞋的方案，請輸出一行"TAK"，否則輸出一行"NIE"。

Sample Input:Sample Output:

4 4 2 1
1 3
2 3
3 3
2 -1

TAK
TAK
NIE
TAK

HINT:

所有事情發生完後，剩下 3 個腳大小為 1 的人，2 個腳大小為 2 的人，3 個腳大小為 3 的人。大小 1 到 4 的溜冰鞋各兩個。
1.腳大小為 1 的兩個人拿大小 1 的溜冰鞋
2.腳大小為 1 的第 3 個人以及另一個腳大小為 2 的人穿大小 2 的溜冰鞋。
3.一個腳大小的 2 的人以及 1 個腳大小為 3 的人穿大小 3 的溜冰鞋。
4.另外兩個腳大小 3 的人穿大小 4 的溜冰鞋。
因此存在一組分配的方案。

Source:

POI 16 Stage 2

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	32768kb
1-ocen	1000ms	32768kb
1	1000ms	32768kb	10
2-ocen	1000ms	32768kb
2	7000ms	32768kb	10
3-ocen	1000ms	32768kb
3	7000ms	32768kb	10
4-ocen	7000ms	32768kb
4	7000ms	32768kb	10
5	7000ms	32768kb	10
6	7000ms	32768kb	10
7	10000ms	32768kb	10
8	10000ms	32768kb	10
9	10000ms	32768kb	10
10-1	10000ms	32768kb	10
10-2	10000ms	32768kb