[AdditionalFile5108.zip](file://AdditionalFile5108.zip?type=additional_file)

P3488 [POI 2009] LYZ-Ice Skates

题目描述

滑冰俱乐部初始有 $[1,n]$ 号码溜冰鞋各 $k$ 双，已知 $x$ 号脚的人可以穿 $[x,x+d]$ 号码的鞋子。

现在有 $m$ 次操作，每次两个数 $r,x$，表示来了 $x$ 个 $r$ 号脚的人，$x$ 为负则表示离开。在每次操作之后，你需要判断溜冰鞋是否足够。

输入格式

第一行 $4$ 个整数 $n,m,k,d$。

接下来 $m$ 行，每行两个整数 $r_i,x_i$，代表一次操作。

输出格式

$m$ 行，每行一个字符串，若此次操作后满足题意则输出 TAK，否则输出 NIE。

输入输出样例 #1

输入 #1

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

输出 #1

TAK
TAK
NIE
TAK

说明/提示

$n\le 2\times 10^5,m\le 5\times 10^5,k\le 10^9,1\le r_i\le n-d,-10^9\le x_i\le 10^9,0\le d<n$

#5108. 「POI2009 R2」冰鞋 Ice Skates

标签: 传统 | 时间限制: 4000 ms | 内存限制: 32 MiB |

题目描述

题目译自 XVI OI Olimpiada Informatyczna – II etap Łyżwy

Bajtazar 经营一家滑冰俱乐部，成员定期聚会训练，统一使用俱乐部提供的冰鞋。冰鞋尺寸从 $1$ 到 $n$ 编号。每位成员的脚型对应特定尺寸 $r$，但可接受尺寸范围为 $r$ 到 $r+d$（容差 $d$）。需注意，成员不可同时穿不同尺寸的冰鞋。

Bajtazar 为俱乐部购置了每种尺寸（$1$ 到 $n$）各 $k$ 副冰鞋。随着时间推移，新成员加入，部分成员退出。Bajtazar 担心每次训练时是否能为所有成员提供合适尺寸的冰鞋。

初始时俱乐部无成员。Bajtazar 提供了一组 $m$ 个事件序列，每事件形如：新增或减少 $x$ 名脚型尺寸为 $r$ 的成员。他希望在每个事件后确认是否能为所有成员分配合适冰鞋。请编写程序，协助他进行判断。

输入格式

第一行包含四个整数 $n, m, k, d$ $(1 \leq n \leq 200000, 1 \leq m \leq 500000, 1 \leq k \leq 10^9, 0 \leq d < n)$，分别表示最大冰鞋尺寸、事件数、每种尺寸的冰鞋副数和脚型尺寸容差。

接下来的 $m$ 行描述事件，第 $i+1$ $(1 \leq i \leq m)$ 行包含两个整数 $r_i, x_i$ $(1 \leq r_i \leq n-d, -10^9 \leq x_i \leq 10^9)$。若 $x_i \geq 0$，表示新增 $x_i$ 名脚型尺寸为 $r_i$ 的成员；若 $x_i < 0$，表示 $-x_i$ 名脚型尺寸为 $r_i$ 的成员退出。保证事件序列合法，即不会退出未加入的成员。

输出格式

输出 $m$ 行，第 $i$ $(1 \leq i \leq m)$ 行包含 TAK 或 NIE，表示第 $i$ 个事件后，Bajtazar 是否能为所有成员分配合适尺寸的冰鞋。

样例

输入

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

输出

TAK
TAK
NIE
TAK

所有事件发生后，俱乐部有三名成员可穿尺寸 $1$ 或 $2$ 的冰鞋，两名成员可穿尺寸 $2$ 或 $3$ 的冰鞋，三名成员可穿尺寸 $3$ 或 $4$ 的冰鞋。在此成员构成下，每种尺寸各两副冰鞋足够分配：

• 两名成员使用尺寸 $1$ 的冰鞋；
• 一名可穿尺寸 $1$ 或 $2$ 的成员和一名可穿尺寸 $2$ 或 $3$ 的成员使用尺寸 $2$ 的冰鞋；
• 一名可穿尺寸 $2$ 或 $3$ 的成员和一名可穿尺寸 $3$ 或 $4$ 的成员使用尺寸 $3$ 的冰鞋；
• 剩余两名成员使用尺寸 $4$ 的冰鞋。