题面

由于是中文题面，题面又不算特别绕，就不在这里说题意了

思路：

首先看到要求的是美味度最小值的最大值。这几乎就是二分答案的标志（除了某些贪心题）。

考虑二分答案之后如何判定是否可行。子问题就变成了：对于给定的不同种类的饮料，从中任选L升，能否用g这么多钱买下。这个子问题显然可以从价格低的饮料开始贪心。暴力贪心的话复杂度是O(n)的，套上外面的二分答案以及更外面的询问次数m，总复杂度$O(nm\lg g)$。

容易发现贪心的过程中有许多重复计算，考虑用带log的数据结构维护。首先可以想到，如果每一次二分答案之后都能有一棵线段树，容易在线段树上二分找到答案。又可以想到，相邻位置的线段树只有一个单点插入的区别，因此可以利用可持久化线段树做。总复杂度$O(n\lg n+m\lg g \lg n)$

(然而创建node的地方忘开longlong导致惨夺15分，第二天早上一起来就看到了问题)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//by Richard
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
using namespace std;
mt19937 rnd(19260817);
const int inf=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int> pii;
///////////////////////read5.1///////////////////////
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
////////////////variables&functions//////////////////
const int maxn=111111,maxvalue=100000;
int n,m;
struct node
{
    node *l,*r;
    LL sp,sv;//sum of price;sum of volume
    node():l(0),r(0),sp(0),sv(0){}
    node(node *ll,node *rr):l(ll),r(rr),sp((ll?ll->sp:0)+(rr?rr->sp:0)),sv((ll?ll->sv:0)+(rr?rr->sv:0)){}
    node(LL v1,LL v2):l(0),r(0),sp(v1),sv(v2){}
};
node *root[maxn];
char memorypool[maxn*sizeof(node)*60];//1 char=1 byte
char *memorypoolptr=memorypool;
inline void* myalloc(size_t size)
{
    return (memorypoolptr+=size)-size;
}
#define newnode new (myalloc(sizeof(node))) node
node* insert(node *x,int k,int limit,int L=1,int R=maxvalue)
{
    if (L==R) 
    {
        if (!x)
        {
            return newnode((LL)k*limit,limit);
        }
        else
        {
            LL temp=x->sv+limit;
            return newnode(temp*k,temp);
        }
    }
    int mid=(L+R)>>1;
    if (k<=mid) return newnode(insert(x?x->l:0,k,limit,L,mid),x?x->r:0);
    else return newnode(x?x->l:0,insert(x?x->r:0,k,limit,mid+1,R));
}
LL query(node *x,LL maxp,int L=1,int R=maxvalue)
{
    if ((!x)||(!maxp)) return 0;
    if (x->sp<=maxp) return x->sv;
    if (L==R) return maxp/L;
    int mid=(L+R)>>1;
    if (!x->l) return x->r?query(x->r,maxp,mid+1,R):0;
    else if (x->l->sp<maxp) return x->l->sv+query(x->r,maxp-x->l->sp,mid+1,R);
    else return query(x->l,maxp,L,mid);
}
struct DATA
{
    int d,p,l;
    bool operator<(const DATA &b)const
    {
        return d>b.d;
    }
}data[maxn];
bool check(const int &mind,const LL &maxp,const LL &minv)
{
    int l=0,r=n;
    while (l<r)
    {
        int mid=(l+r+1)>>1;
        if (data[mid].d>=mind) l=mid;
        else r=mid-1;
    }
    //cerr<<"check mind="<<mind<<" maxp="<<maxp<<" minv="<<minv<<" l="<<l<<endl;
    int tt=query(root[l],maxp);
    // cout<<"mind="<<mind<<" l="<<l<<" res="<<tt<<endl;
    return tt>=minv;
}
int main()
{
    read(n,m);
    rep(i,1,n) read(data[i].d,data[i].p,data[i].l);
    sort(data+1,data+n+1);
    root[0]=newnode();
    rep(i,1,n) root[i]=insert(root[i-1],data[i].p,data[i].l);
    rep(i,1,m)
    {
        LL g,L;
        read(g,L);
        // if (root[n]->sv<L||g<L||query(root[n],g)<L)
        // {
            // puts("-1");
            // continue;
        // }
        int l=0,r=100000;
        while (l<r)
        {
            int mid=(l+r+1)>>1;
            if (check(mid,g,L)) l=mid;//if possible, ans can be larger(better)
            else r=mid-1;
        }
        if (l==0) l=-1;
        printf("%d\n",l);
    }
    return 0;
}