题目描述
小 R 热衷于做黑暗料理，尤其是混合果汁。
商店里有 nn 种果汁，编号为 0,1,\cdots,n-10,1,⋯,n−1 。 ii 号果汁的美味度是 d_idi ，每升价格为 p_ipi 。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中， ii 号果汁最多只能添加 l_ili 升。
现在有 mm 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 jj 个小朋友希望他得到的混合果汁总价格不大于 g_jgj ，体积不小于 L_jLj 。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。
输入输出格式
输入格式：
输入第一行包含两个正整数 n, mn,m ，表示果汁的种数和小朋友的数量。接下来 nn 行，每行三个正整数 d_i, p_i, l_idi,pi,li ，表示 ii 号果汁的美味度为 d_idi ，每升价格为 p_ipi ，在一瓶果汁中的添加上限为 l_ili 。
接下来 mm 行依次描述所有小朋友：每行两个数正整数 g_j, L_jgj,Lj 描述一个小朋友，表示他最多能支付 g_jgj 元钱，他想要至少 L_jLj 升果汁。
输出格式：
对于所有小朋友依次输出：对于每个小朋友，输出一行，包含一个整数，表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求，则输出 -1−1 。
输入输出样例
3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10
3
2
-1
1
说明
对于所有的测试数据，保证 n, m \le 100000n,m≤100000 ， 1 \le d_i,p_i,l_i \le 10^5, 1 \le g_j, L_j \le 10^{18}1≤di,pi,li≤105,1≤gj,Lj≤1018 。
首先二分一波美味度
然后我们需要在美味度大于当前值的果汁中取，很明显是价格越小的越先取到
但是直接这样做复杂度是$O(n^2log^2n)$的
对于任意一个美味度，我们可以把它能取得的价格用线段树维护
然后可持久化一下就好了
时间复杂度$O(nlog^2n)$
#include<cstdio>
#include<algorithm> using namespace std;
const int MAXN = * 1e6 + ;
inline int read() {
char c = getchar(); int x = , f = ;
while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int N, M;
int root[MAXN];
struct Juice {
int D, P, L;
bool operator < (const Juice &rhs) const{
return D < rhs.D;
}
}a[MAXN];
struct node {
int ls, rs, tj, mon;
}T[MAXN];
int limit = , tot = ;
#define ls(x) T[x].ls
#define rs(x) T[x].rs
int insert(int &now, int pre, int l, int r, int pos, int val) {
now = ++tot;
T[now].ls = T[pre].ls; T[now].rs = T[pre].rs; T[now].tj = T[pre].tj + val, T[now].mon = T[pre].mon + val * pos;
if(l == r) return now;
int mid = (l + r) >> ;
if(pos <= mid) T[now].ls = insert(T[now].ls, T[pre].ls, l, mid, pos, val);
else T[now].rs = insert(T[now].rs, T[pre].rs, mid + , r, pos, val);
return now;
}
int Query(int now, int pre, int l, int r, int money) {
if(l == r) {return min(money / l, T[now].tj - T[pre].tj);}
int used = T[ls(now)].mon - T[ls(pre)].mon, mid = l + r >> ;
if(used <= money)
return Query(rs(now), rs(pre), mid + , r, money - used) + T[ls(now)].tj - T[ls(pre)].tj;
else
return Query(ls(now), ls(pre), l, mid, money);
}
int check(int pos, int G, int L) {
int ans = Query(root[N], root[pos - ], , limit, G);
return ans >= L;
}
int Solve(int G, int L) {
int l = , r = N, ans = ;
while(l <= r) {
int mid = l + r >> ;
if(check(mid, G, L)) ans = mid, l = mid + ;
else r = mid - ;
}
return ans == ? - : a[ans].D;
}
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
N = read(), M = read();
for(int i = ; i <= N; i++)
a[i].D = read(), a[i].P = read(), a[i].L = read(), limit = max(a[i].P, limit);
sort(a + , a + N + );
for(int i = ; i <= N; i++)
insert(root[i], root[i - ], , limit, a[i].P, a[i].L);
while(M--) {
int G = read(), L = read();
printf("%lld\n", Solve(G, L));
}
}