#P18793. [Omi2022] 磨牙症

[Omi2022] 磨牙症

[Omi2022] 磨牙症

题目描述

有 NN 颗牙齿。第 ii 颗牙齿的硬度为 DiD_i,每次受损增加的伤害为 AiA_i,每次恢复减少的伤害为 BiB_i,能承受的伤害上限为 MiM_i。

你已经知道接下来 TT 个晚上的咬合力度 F1,F2,…,FTF_1,F_2,\ldots,F_T。

每颗牙齿初始伤害均为 00。对于尚未脱落的第 ii 颗牙齿,第 jj 个晚上按以下规则更新伤害:

  • 若 Fj>DiF_j>D_i,伤害增加 AiA_i;
  • 若 Fj≤DiF_j\le D_i,伤害减少 BiB_i,但最低只能降到 00。

如果更新后伤害达到或超过 MiM_i,这颗牙齿立即脱落,之后不会重新长回。

请判断每颗牙齿是否会在这 TT 个晚上中的某个时刻脱落。

输入格式

第一行包含两个整数 N,TN,T。

接下来 NN 行,第 ii 行包含四个整数 Di,Ai,Bi,MiD_i,A_i,B_i,M_i。

最后一行包含 TT 个整数 F1,F2,…,FTF_1,F_2,\ldots,F_T。

输出格式

输出一行 NN 个整数。如果第 ii 颗牙齿曾经脱落,输出 1;否则输出 0。整数之间以空格分隔。

样例输入

3 5
1 2 3 15
5 10 5 10
3 3 4 5
4 2 8 3 4

样例输出

0 1 0

样例说明

第一颗牙齿每天受损,五晚后伤害为 10<1510<15,没有脱落。

第二颗牙齿在第三晚受到 1010 点伤害,恰好达到上限,因而脱落。

第三颗牙齿的伤害依次为 3,0,3,0,33,0,3,0,3,没有达到上限 55。

数据范围与分组

  • 1≤N≤2500001\le N\le250000;
  • 1≤T≤100001\le T\le10000;
  • 1≤Ai,Bi≤201\le A_i,B_i\le20;
  • 1≤Di,Fj≤1091\le D_i,F_j\le10^9;
  • 1≤Mi≤1061\le M_i\le10^6。
分值 额外限制
18 N,T≤1000N,T\le1000
24 所有牙齿的 DiD_i 相同、AiA_i 相同且 BiB_i 相同;MiM_i 可以不同
27 对所有牙齿均有 Ai=BiA_i=B_i
31 无额外限制