Solution
最小的最大,显然二分答案。
考虑二分完后怎么判断?有一个显然的贪心——把所有能取的物品按价格排序,从小到大尽量取,如果最后取到的大于要求的,那么就是可行的。
这里有多个询问就考虑整体二分。
那么每次暴力排序不行,上述过程其实还可以用数据结构来实现。可以用树状数组来维护某一段价格的值,然后在树状数组上二分。
这里有一些实现细节:
-
整体二分并没有每次取答案,而是最后递归到的即为答案,所以这道题要求最大值就要向上取整,每次分区间时分成:
[l,mid-1]
和[mid,r]
。 -
这里我们在求右半边的答案时要删掉左半边的值,所以我们先递归左半边,然后回滚,然后再递归右半边。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
#define getchar()(ip1==ip2&&(ip2=(ip1=ibuf)+fread(ibuf,1,1<<21,stdin),ip1==ip2)?EOF:*ip1++)
char ibuf[1<<21],*ip1=ibuf,*ip2=ibuf;
template<typename T>
inline void read(T &x)
{
static char ch;bool f=1;
for(x=0,ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=0;
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());x=f?x:-x;
}
template<typename T>
void print(T x)
{
if (x<0) x=-x,putchar('-');
if (x>9) print(x/10);
putchar(x%10+48);
}
struct node{
ll val, prc, lim;
int id;
}p[MAXN], q[MAXN];
int num;
int n, m;
int d[MAXN], prc[MAXN], lim[MAXN], b[MAXN], tot;
ll c1[MAXN], c2[MAXN];
ll g[MAXN], L[MAXN], val[MAXN];
int ans[MAXN];
bool mark[MAXN];
int lg[MAXN];
inline void add(int x, ll v1, ll v2) {
while (x <= tot) c1[x] += v1 * v2, c2[x] += v2, x += (x & -x);
}
void solve(int l, int r, int x, int y) {
if (x > y) return;
if (l == r) {
if (l == 0) for (int i = x; i <= y; i++) ans[p[i].id] = -1;
else for (int i = x; i <= y; i++) ans[p[i].id] = l;
return;
}
int cnt = 0;
int mid = (l + r + 1) >> 1;
for (int i = x; i <= y; i++) {
if (p[i].id == -1) {
if (p[i].val >= mid) add(p[i].prc, b[p[i].prc], p[i].lim), val[p[i].prc] += p[i].lim, mark[i] = false;
else mark[i] = true, cnt++;
} else {
ll nowp = 0, nowv = 0;
ll pos = 0;
for (int j = lg[tot - pos] + 1; j >= 0; j--) {
if (pos + (1 << j) > tot) continue;
if (nowp + c1[pos + (1 << j)] <= p[i].prc) {
nowp += c1[pos + (1 << j)];
nowv += c2[pos + (1 << j)];
pos += (1 << j);
}
}
if (pos < tot) {
ll tmp = min((p[i].prc - nowp) / b[pos + 1], val[pos + 1]);
nowv += tmp;
nowp += tmp * b[pos + 1];
}
if (nowv >= p[i].lim) mark[i] = false;
else mark[i] = true, cnt++;
}
}
int L = 0, R = cnt;
for (int i = x; i <= y; i++) {
if (mark[i]) q[++L] = p[i];
else q[++R] = p[i];
}
for (int i = x; i <= y; i++) p[i] = q[i - x + 1];
solve(l, mid - 1, x, x + cnt - 1);
for (int i = x; i <= y; i++) if (p[i].id <= n) if (p[i].val >= mid) add(p[i].prc, b[p[i].prc], -p[i].lim), val[p[i].prc] -= p[i].lim;
solve(mid, r, x + cnt, y);
}
int main() {
int mx = 0;
read(n); read(m);
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; i++) {
read(d[i]); read(prc[i]); read(lim[i]);
mx = max(mx, d[i]);
b[++tot] = prc[i];
}
sort(b + 1, b + 1 + tot);
tot = unique(b + 1, b + 1 + tot) - b - 1;
for (int i = 1; i <= n; i++) {
prc[i] = lower_bound(b + 1, b + 1 + tot, prc[i]) - b;
num++;
p[num] = node{d[i], prc[i], lim[i], -1};
}
for (int i = 1; i <= m; i++) {
read(g[i]); read(L[i]);
num++;
p[num] = node{0, g[i], L[i], i};
}
solve(0, mx, 1, num);
for (int i = 1; i <= m; i++) print(ans[i]), putchar('\n');
return 0;
}