题目描述

小 R 热衷于做黑暗料理,尤其是混合果汁。

商店里有 

n

 种果汁,编号为 

0,1,\cdots,n-1

  

i

 号果汁的美味度是 

d_i

 ,每升价格为 

p_i

 。小 R 在制作混合果汁时,还有一些特殊的规定,即在一瓶混合果汁中, 

i

 号果汁最多只能添加 

l_i

 升。

现在有 

m

 个小朋友过来找小 R 要混合果汁喝,他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中,第 

j

 个小朋友希望他得到的混合果汁总价格不大于 

g_j

 ,体积不小于 

L_j

 。在上述这些限制条件下,小朋友们还希望混合果汁的美味度尽可能地高,一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

输入输出格式

输入格式:

输入第一行包含两个正整数 

n, m

 ,表示果汁的种数和小朋友的数量。接下来 

n

 行,每行三个正整数 

d_i, p_i, l_i

 ,表示 

i

号果汁的美味度为 

d_i

 ,每升价格为 

p_i

 ,在一瓶果汁中的添加上限为 

l_i

 

接下来 

m

 行依次描述所有小朋友:每行两个数正整数 

g_j, L_j

 描述一个小朋友,表示他最多能支付 

g_j

 元钱,他想要至少 

L_j

 升果汁。

输出格式:

对于所有小朋友依次输出:对于每个小朋友,输出一行,包含一个整数,表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求,则输出 

-1

 

输入输出样例

输入样例#1: 复制

输出样例#1: 复制

说明

对于所有的测试数据,保证 

n, m \le 100000

  

1 \le d_i,p_i,l_i \le 10^5, 1 \le g_j, L_j \le 10^{18}

 

测试点编号

n=

m=

其他限制
1,2,3

10

10

4,5,6

500

500

7,8,9

5000

5000

10,11,12

100000

100000

p_i=1

13,14,15

100000

100000

l_i=1

16,17,18,19,20

100000

100000

ctsc的水题..mdzz蒟蒻我部分分就写的正解 以为自己没能力就每写x

考虑二分一下这个d 然后看一下这个范围内花最小代价凑出L升果汁需要花的钱 看是否满足大于我能花的最多的钱  如果大于 说明我这个选择范围有点小 需要把可选择的d的范围进一步扩大才可以

 

分类: 主席树二分

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论