[loj2555][CTSC2018]混合果汁

ryznb

题意

懒得写了拉题面

思路

显然二分最小美味值。

建立关于单价的主席树。

Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
typedef long long LL;
const int N = 100010,alpha = 20,S = 32768;
char buf[S];int len = 0,pos = 0;
char buf2[S],*pp = buf2;
inline char __getchar()
{
if(pos == len)pos = 0,len = fread(buf,1,S,stdin);if(pos == len)return '\0';
return buf[pos++];
}
inline void __putchar(char c) {if(pp == buf2 + S)fwrite(buf2,1,S,stdout),pp = buf2;*pp++ = c;}
inline void flush(){fwrite(buf2,1,pp - buf2,stdout);}
inline void putll(LL x)
{
if(x < 0){__putchar('-');x = -x;}
if(!x) {__putchar('0');return;}
if(x > 9) putll(x / 10);
__putchar((x % 10) ^ '0');
}
inline int getint()
{
int r = 0,s = 1;char c = __getchar();for(;!isdigit(c);c = __getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = __getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
inline LL getll()
{
LL r = 0,s = 1;char c = __getchar();for(;!isdigit(c);c = __getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = __getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
struct Info{int d,p,l;inline friend bool operator < (const Info &a,const Info &b){return a.d < b.d;}}info[N];
struct FotileTree
{
int root[N],lc[N * alpha],rc[N * alpha],sz;LL vol[N * alpha],sum[N * alpha];
FotileTree(){sz = 0;}
inline void insert(int &x,int y,int l,int r,int p,int v)
{
x = ++sz;lc[x] = lc[y];rc[x] = rc[y];vol[x] = vol[y];sum[x] = sum[y];
vol[x] += v;sum[x] += 1LL * p * v;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) insert(lc[x],lc[y],l,mid,p,v);
else insert(rc[x],rc[y],mid + 1,r,p,v);
}
inline LL query(int x,int y,int l,int r,LL g)
{
if(l == r) return std::min(g / l,vol[x] - vol[y]);
int mid = (l + r) >> 1;
LL dv = vol[lc[x]] - vol[lc[y]],ds = sum[lc[x]] - sum[lc[y]];
if(ds == g) return dv;
else if(ds > g) return query(lc[x],lc[y],l,mid,g);
else return dv + query(rc[x],rc[y],mid + 1,r,g - ds);
}
}PT;
int n,m,mx;int tmp[N];
inline bool judge(int k,LL g,LL l){return PT.query(PT.root[n],PT.root[tmp[k] - 1],1,mx,g) >= l;}
int main()
{
n = getint(),m = getint();
for(int i = 1;i <= n;i++) info[i].d = getint(),mx = std::max(mx,info[i].p = getint()),info[i].l = getint();
std::sort(info + 1,info + n + 1);
for(int i = 1;i <= n;i++)
{
int d = info[i].d,p = info[i].p,l = info[i].l;
if(d != info[tmp[tmp[0]]].d) tmp[++tmp[0]] = i;
PT.insert(PT.root[i],PT.root[i - 1],1,mx,p,l);
}
while(m--)
{
LL g = getll(),v = getll();
int l = 1,r = tmp[0],ans = -1;
while(l <= r)
{
int mid = (l + r) >> 1;
if(judge(mid,g,v)){l = mid + 1;ans = info[tmp[mid]].d;}
else r = mid - 1;
}
putll(ans);__putchar(10);
}
flush();
return 0;
}