洛谷P4602 [CTSC2018]混合果汁(主席树)

2018-06-17 20:35:30来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

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

商店里有 nn 种果汁,编号为 0,1,\cdots,n-10,1,?,n1 。 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? 升果汁。

 

输出格式:

 

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

 

输入输出样例

输入样例#1: 复制
3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10
输出样例#1: 复制
3
2
-1
1

说明

对于所有的测试数据,保证 n, m \le 100000n,m100000 , 1 \le d_i,p_i,l_i \le 10^5, 1 \le g_j, L_j \le 10^{18}1di?,pi?,li?105,1gj?,Lj?1018 。

 

首先二分一波美味度

然后我们需要在美味度大于当前值的果汁中取,很明显是价格越小的越先取到

但是直接这样做复杂度是$O(n^2log^2n)$的

对于任意一个美味度,我们可以把它能取得的价格用线段树维护

然后可持久化一下就好了

时间复杂度$O(nlog^2n)$

 

#include<cstdio>
#include<algorithm>

using namespace std;
const int MAXN = 2 * 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1; 
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', 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 = 0, tot = 0;
#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) >> 1;
    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 + 1, 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 >> 1;
    if(used <= money) 
        return Query(rs(now), rs(pre), mid + 1, 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 - 1], 0, limit, G);
    return ans >= L;
}
int Solve(int G, int L) {
    int l = 1, r = N, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid, G, L)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans == 0 ? -1 : a[ans].D;
}
main() {
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    #endif
    N = read(), M = read();
    for(int i = 1; i <= N; i++)
        a[i].D = read(), a[i].P = read(), a[i].L = read(), limit = max(a[i].P, limit);
    sort(a + 1, a + N + 1);
    for(int i = 1; i <= N; i++) 
        insert(root[i], root[i - 1], 0, limit, a[i].P, a[i].L);
    while(M--) {
        int G = read(), L = read();
        printf("%lld\n", Solve(G, L));
    }
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Windows 使用 Visual Studio 编译 caffe

下一篇:关于CCR测评器的自定义校验器(Special Judge)