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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
const int N = 1e5;
int n,m,ans[maxn],p;
struct pps {int d,p,l;}a[maxn];
struct Q {int g,l,id;}q[maxn],q1[maxn],q2[maxn];
int cmp(pps x,pps y) {return x.d<y.d;}
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
struct segment_tree {
int w[maxn<<2],s[maxn<<2];
void modify(int p,int l,int r,int x,int v) {
if(l==r) return w[p]+=v,s[p]=l*w[p],void();
if(x<=mid) modify(ls,l,mid,x,v);
else modify(rs,mid+1,r,x,v);
s[p]=s[ls]+s[rs],w[p]=w[ls]+w[rs];
}
int query(int p,int l,int r,int v) {
if(l==r) return min(v/l,w[p]);
if(s[ls]>=v) return query(ls,l,mid,v);
return w[ls]+query(rs,mid+1,r,v-s[ls]);
}
}T;
void solve(int l,int r,int ql,int qr) {
if(ql>qr) return;
if(l==r) {
for(int i=ql;i<=qr;i++) ans[q[i].id]=a[l].d;
return ;
}
while(p>mid+1) p--,T.modify(1,-1,N,a[p].p,a[p].l);
while(p<mid+1) T.modify(1,-1,N,a[p].p,-a[p].l),p++;
int t1=0,t2=0;
for(int i=ql;i<=qr;i++) {
if(T.query(1,-1,N,q[i].g)>=q[i].l) q2[++t2]=q[i];
else q1[++t1]=q[i];
}
for(int i=1;i<=t1;i++) q[ql+i-1]=q1[i];
for(int i=1;i<=t2;i++) q[ql+t1+i-1]=q2[i];
solve(l,mid,ql,ql+t1-1),solve(mid+1,r,ql+t1,qr);
}
signed main() {
read(n),read(m);
for(int i=1;i<=n;i++) read(a[i].d),read(a[i].p),read(a[i].l);
a[++n]=(pps){-1,0,(int)1e18};p=n+1;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=m;i++) read(q[i].g),read(q[i].l),q[i].id=i;
solve(1,n,1,m);
for(int i=1;i<=m;i++) write(ans[i]);
return 0;
}
|