[POI2009]Lyz

[POI2009]Lyz

Time Limit:10000MS  Memory Limit:165536K
Total Submit:56 Accepted:16
Case Time Limit:2000MS

Description

初始时滑冰俱乐部有1到n号的溜冰鞋各k双。已知x号脚的人可以穿x到x+d的溜冰鞋。

有m次操作,每次包含两个数ri,xi代表来了xi个ri号脚的人。xi为负,则代表走了这么多人。

对于每次操作,输出溜冰鞋是否足够。

Input

n m k d ( 1≤n≤200,000 , 1≤m≤500,000 , 1≤k≤109 , 0≤d≤n )

ri xi ( 1≤i≤m, 1≤ri≤n-d , |xi|≤109 )

Output

对于每个操作,输出一行,TAK表示够 NIE表示不够。

Sample Input

4 4 2 1

1 3

2 3

3 3

2 -1

Sample Output

TAK

TAK

NIE

TAK

Source
额。。这个题目有二分图匹配的感觉。那么根据Hall定理,对于任何一个子集,他的临集的大小必须要大于它的大小。。
那么设ti为脚为i号的人数
对于ta到tb,它们临集的大小显然是(b-a+1+d)*k
那么需要知道是不是对任何一个连续子序列都满足这个。。
变形一下设t’a=ta-k
那么Sum(ta..b)<=(b-a+1+d)*k
<=>
Sum(t’a..b)<=d*k
。。。。可以发现只要维护t’的最大子序列和就OK了T_T。。
这显然是最简单的线段树。。
发代码也麻烦。。。我的马甲nimendongde的密码是123456.。。。
自己去看吧T_T。。

One thought on “[POI2009]Lyz

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>