BZOJ 5343
福利题。
对于每一个询问可以二分$d$，然后把满足条件的果汁按照$p$从小到大排序贪心地取$L$升看看满不满足价格的条件。
那么按照$p$建立权值主席树，$chk$的时候在主席树上走一走算出价格即可。
当然也可以整体二分。
时间复杂度都是$O(nlog^2n)$。
Code：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll; const int N = 1e5 + ;
const ll inf = 1LL << ; int n, qn, tot = , pos[N], buc[N]; struct Item {
int d, cost, lim; inline Item(int D = , int Cost = , int Lim = ) {
d = D, cost = Cost, lim = Lim;
} friend bool operator < (const Item x, const Item y) {
return x.d > y.d;
} } a[N]; namespace Fread {
const int L = << ; char buffer[L], *S, *T; inline char Getchar() {
if(S == T) {
T = (S = buffer) + fread(buffer, , L, stdin);
if(S == T) return EOF;
}
return *S++;
} template <class T>
inline void read(T &X) {
char ch; T op = ;
for(ch = Getchar(); ch > '' || ch < ''; ch = Getchar())
if(ch == '-') op = -;
for(X = ; ch >= '' && ch <= ''; ch = Getchar())
X = (X << ) + (X << ) + ch - '';
X *= op;
} } using namespace Fread; namespace Fwrite {
const int L = << ; char buf[L], *pp = buf; void Putchar(const char c) {
if(pp - buf == L) fwrite(buf, , L, stdout), pp = buf;
*pp++ = c;
} template<typename T>
void print(T x) {
if(x < ) {
Putchar('-');
x = -x;
}
if(x > ) print(x / );
Putchar(x % + '');
} void fsh() {
fwrite(buf, , pp - buf, stdout);
pp = buf;
} template <typename T>
inline void write(T x, char ch = ) {
print(x);
if (ch != ) Putchar(ch);
fsh();
} } using namespace Fwrite; namespace SegT {
struct Node {
int lc, rc;
ll sum, cnt;
} s[N * ]; int root[N], nodeCnt = ; #define lc(p) s[p].lc
#define rc(p) s[p].rc
#define sum(p) s[p].sum
#define cnt(p) s[p].cnt
#define mid ((l + r) >> 1) void ins(int &p, int l, int r, int x, int v, int pre) {
s[p = ++nodeCnt] = s[pre];
cnt(p) += 1LL * v, sum(p) += 1LL * v * buc[x];
if (l == r) return; if (x <= mid) ins(lc(p), l, mid, x, v, lc(pre));
else ins(rc(p), mid + , r, x, v, rc(pre));
} ll query(int p, int l, int r, ll cur) {
if (l == r) return cur > cnt(p) ? inf : cur * buc[l];
ll now = cnt(lc(p));
if (cur <= now) return query(lc(p), l, mid, cur);
else return sum(lc(p)) + query(rc(p), mid + , r, cur - now);
} #undef mid } using namespace SegT; inline bool chk(int mid, ll x, ll y) {
if (cnt(root[pos[a[mid].d]]) < y) return ;
ll now = query(root[pos[a[mid].d]], , tot, y);
return now <= x;
} int main() {
#ifndef ONLINE_JUDGE
freopen("Sample.txt", "r", stdin);
#endif read(n), read(qn);
for (int i = ; i <= n; i++) {
read(a[i].d), read(a[i].cost), read(a[i].lim);
buc[++tot] = a[i].cost;
} sort(buc + , buc + + tot);
tot = unique(buc + , buc + + tot) - buc - ;
for (int i = ; i <= n; i++)
a[i].cost = lower_bound(buc + , buc + + tot, a[i].cost) - buc; sort(a + , a + + n);
for (int i = ; i <= n; i++) {
ins(root[i], , tot, a[i].cost, a[i].lim, root[i - ]);
pos[a[i].d] = i;
} for (ll x, y; qn--; ) {
read(x), read(y);
/* if (y > cnt(root[n])) {
puts("-1");
continue;
} */ int ln = , rn = n, mid, res = ;
for (; ln <= rn; ) {
mid = (ln + rn) / ;
if (chk(mid, x, y)) rn = mid - , res = mid;
else ln = mid + ;
} write((!res) ? - : a[res].d, '\n');
} return ;
}