#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*typedef int64_t int;*/
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
bool cmp(pair<pair<int,int>,pair<int,int>> &ac,pair<pair<int,int>,pair<int,int>> &cc){
return ac.b.a<=cc.b.a;
}
bool cmp2(pair<pair<int,int>,int> &ac,pair<pair<int,int>,int> &cc){
return ac.a.a+ac.a.b<=cc.a.a+cc.a.b;
}
bool cmp3(pair<pair<int,int>,int> &ac,pair<pair<int,int>,int> &cc){
return ac.a.a<=cc.a.a;
}
vector<int> tree[400001];
vector<pair<int,int>> ss[400001];
vector<int> indd[400001];
pair<int,int> bb[100001];
void u(int no,int i,int j){
while(i<=tree[no].size()){
tree[no][i]+=j;
i+=(i&-i);
}
}
int st(int no,int i){
int tot=0;
while(i>0){
tot+=tree[no][i];
i-=(i&-i);
}
return tot;
}
void build(int no,int l,int r){
for(int i=l;i<=r+1;i++){
tree[no].pb(0);
indd[no].pb(0);
}
if(r>l){
int mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
int ind=0;
int ind2=0;
int ind3=0;
while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
if(ss[no*2+1][ind].a<ss[no*2+2][ind2].a){
ss[no].pb(ss[no*2+1][ind]);
indd[no][ss[no*2+1][ind].b-l]=ind3;
ind+=1;
ind3+=1;
}
else{
ss[no].pb(ss[no*2+2][ind2]);
indd[no][ss[no*2+2][ind2].b-l]=ind3;
ind2+=1;
ind3+=1;
}
}
while(ind<ss[no*2+1].size() ){
ss[no].pb(ss[no*2+1][ind]);
indd[no][ss[no*2+1][ind].b-l]=ind3;
ind+=1;
ind3+=1;
}
while(ind2<ss[no*2+2].size()){
ss[no].pb(ss[no*2+2][ind2]);
indd[no][ss[no*2+2][ind2].b-l]=ind3;
ind2+=1;
ind3+=1;
}
}
else{
ss[no].pb({bb[l].b,l});
}
}
void update(int no,int l,int r,int ind){
if(ind<l or ind>r){
return;
}
u(no,indd[no][ind-l]+1,1);
if(r>l){
int mid=(l+r)/2;
update(no*2+1,l,mid,ind);
update(no*2+2,mid+1,r,ind);
}
}
int kk;
int cp;
int query(int no,int l,int r){
if(bb[r].a<kk){
return 0;
}
if(bb[l].a>=kk){
if(ss[no][r-l].a<cp){
return 0;
}
int low=0;
int high=r-l;
while(low<high-1){
int mid=(low+high)/2;
if(ss[no][mid].a>=cp){
high=mid;
}
else{
low=mid+1;
}
}
int dd=high;
if(ss[no][low].a>=cp){
dd=low;
}
int xx=st(no,r-l+1);
if(dd>0){
xx-=st(no,dd);
}
return xx;
}
else{
int mid=(l+r)/2;
return query(no*2+1,l,mid)+query(no*2+2,mid+1,r);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n,q;
cin>>n>>q;
pair<pair<int,int>,int> aa[n];
for(int i=0;i<n;i++){
cin>>aa[i].a.a>>aa[i].a.b;
}
sort(aa,aa+n,cmp3);
for(int i=0;i<n;i++){
aa[i].b=i;
}
for(int i=0;i<n;i++){
bb[i]=aa[i].a;
}
sort(aa,aa+n,cmp2);
int pp,bb,cc;
vector<pair<pair<int,int>,pair<int,int>>> qq;
for(int i=0;i<q;i++){
cin>>pp>>bb>>cc;
qq.pb({{pp,bb},{cc,i}});
}
sort(qq.begin(),qq.end(),cmp);
int pos=n-1;
int ans[q];
build(0,0,n-1);
// cout<<33<<endl;
for(int ii=q-1;ii>=0;ii--){
int ba=qq[ii].b.a;
while(pos>=0){
if(aa[pos].a.a+aa[pos].a.b>=ba){
update(0,0,n-1,aa[pos].b);
// cout<<aa[pos].b<<" "<<ii<<endl;
pos-=1;
}
else{
break;
}
}
kk=qq[ii].a.a;
cp=qq[ii].a.b;
int ans4=query(0,0,n-1);
ans[qq[ii].b.b]=ans4;
}
for(int i=0;i<q;i++){
cout<<ans[i]<<endl;
}
return 0;
}
Compilation message
examination.cpp: In function 'void u(int, int, int)':
examination.cpp:24:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<=tree[no].size()){
~^~~~~~~~~~~~~~~~~
examination.cpp: In function 'void build(int, int, int)':
examination.cpp:49:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
~~~^~~~~~~~~~~~~~~~~~
examination.cpp:49:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:63:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<ss[no*2+1].size() ){
~~~^~~~~~~~~~~~~~~~~~
examination.cpp:69:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind2<ss[no*2+2].size()){
~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 2 |
Correct |
21 ms |
28416 KB |
Output is correct |
| 3 |
Correct |
22 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 5 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 6 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 7 |
Correct |
31 ms |
29952 KB |
Output is correct |
| 8 |
Correct |
31 ms |
29952 KB |
Output is correct |
| 9 |
Correct |
32 ms |
30080 KB |
Output is correct |
| 10 |
Correct |
30 ms |
29952 KB |
Output is correct |
| 11 |
Incorrect |
33 ms |
29944 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
124 ms |
64976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
124 ms |
64976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 2 |
Correct |
21 ms |
28416 KB |
Output is correct |
| 3 |
Correct |
22 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 5 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 6 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 7 |
Correct |
31 ms |
29952 KB |
Output is correct |
| 8 |
Correct |
31 ms |
29952 KB |
Output is correct |
| 9 |
Correct |
32 ms |
30080 KB |
Output is correct |
| 10 |
Correct |
30 ms |
29952 KB |
Output is correct |
| 11 |
Incorrect |
33 ms |
29944 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
