#2794. [POI2012] Cloakroom

[POI2012] Cloakroom

题目描述

nn 件物品,每件物品有三个属性 ai,bi,cia_i,b_i,c_iai<bia_i<b_i)。 再给出 qq 个询问,每个询问由非负整数 m,k,sm,k,s 组成,问是否能够选出某些物品使得:

  1. 对于每个选的物品 ii,满足 aima_i\leq mbi>m+sb_i>m+s
  2. 所有选出物品的 cic_i 的和正好是 kk

输入格式

第一行一个整数 nn
接下来 nn 行每行三个整数,分别表示 ci,ai,bic_i,a_i,b_i
下面一行一个整数 qq
接下来 qq 行每行三个整数 m,k,sm,k,s

输出格式

输出 qq 行,每行为 TAKNIE,分别表示这组询问有解/无解。

5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5
TAK
NIE
TAK
TAK
NIE

数据规模与约定

对于 100%100\% 的数据,1n,ci1031\leq n,c_i\leq 10^31ai<bi1091\leq a_i<b_i\leq 10^91m1091\leq m\leq 10^91k1051\leq k\leq 10^51q1061\leq q\leq 10^60s1090\leq s\leq 10^9