#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
bool cmp(pair<pair<llo,llo>,pair<llo,llo>> ac,pair<pair<llo,llo>,pair<llo,llo>> cc){
return ac.b.a<=cc.b.a;
}
bool cmp2(pair<pair<llo,llo>,llo> ac,pair<pair<llo,llo>,llo> cc){
return ac.a.a+ac.a.b<=cc.a.a+cc.a.b;
}
bool cmp3(pair<pair<llo,llo>,llo> ac,pair<pair<llo,llo>,llo> cc){
return ac.a.a<cc.a.a;
}
vector<llo> tree[400001];
vector<pair<llo,llo>> ss[400001];
vector<llo> indd[400001];
pair<llo,llo> bb[100001];
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
// freopen((name+".out").c_str(),"w",stdout);
}
void u(llo no,llo i,llo j){
while(i<tree[no].size()){
tree[no][i]+=j;
i+=(i&-i);
}
}
llo st(llo no,llo i){
llo tot=0;
while(i>0){
tot+=tree[no][i];
i-=(i&-i);
}
return tot;
}
void build(llo no,llo l,llo r){
for(llo i=l;i<=r+2;i++){
tree[no].pb(0);
indd[no].pb(0);
}
if(r>l){
llo mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
llo ind=0;
llo ind2=0;
llo 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(llo no,llo l,llo r,llo ind){
if(ind<l or ind>r){
return;
}
u(no,indd[no][ind-l]+1,1);
if(r>l){
llo mid=(l+r)/2;
update(no*2+1,l,mid,ind);
update(no*2+2,mid+1,r,ind);
}
}
llo kk;
llo cp;
llo query(llo no,llo l,llo r){
if(bb[r].a<kk){
return 0;
}
if(bb[l].a>=kk){
if(ss[no][r-l].a<cp){
return 0;
}
llo low=0;
llo high=r-l;
while(low<high-1){
llo mid=(low+high)/2;
if(ss[no][mid].a>=cp){
high=mid;
}
else{
low=mid+1;
}
}
llo dd=high;
if(ss[no][low].a>=cp){
dd=low;
}
llo xx=st(no,r-l+1);
if(dd>0){
xx-=st(no,dd);
}
return xx;
}
else{
llo 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);
llo n,q;
//setIO("11");
cin>>n>>q;
vector<pair<pair<llo,llo>,llo>> aa;
llo mm,nn;
for(llo i=0;i<n;i++){
cin>>mm>>nn;
aa.pb({{mm,nn},0});
}
sort(aa.begin(),aa.end(),cmp3);
for(llo i=0;i<n;i++){
aa[i].b=i;
}
for(llo i=0;i<n;i++){
bb[i]=aa[i].a;
}
sort(aa.begin(),aa.end(),cmp2);
llo pp,bc,cc;
vector<pair<pair<llo,llo>,pair<llo,llo>>> qq;
for(llo i=0;i<q;i++){
cin>>pp>>bc>>cc;
qq.pb({{pp,bc},{cc,i}});
}
sort(qq.begin(),qq.end(),cmp);
llo pos=n-1;
llo ans[q];
build(0,0,n-1);
// cout<<33<<endl;
for(llo ii=q-1;ii>=0;ii--){
llo 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;
llo ans4=query(0,0,n-1);
ans[qq[ii].b.b]=ans4;
}
for(llo i=0;i<q;i++){
cout<<ans[i]<<endl;
}
return 0;
}
Compilation message
examination.cpp: In function 'void u(llo, llo, llo)':
examination.cpp:29:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<tree[no].size()){
~^~~~~~~~~~~~~~~~
examination.cpp: In function 'void build(llo, llo, llo)':
examination.cpp:54: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:54: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:68:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<ss[no*2+1].size() ){
~~~^~~~~~~~~~~~~~~~~~
examination.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind2<ss[no*2+2].size()){
~~~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'void setIO(std::__cxx11::string)':
examination.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen((name+".in").c_str(),"r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 2 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 3 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 5 |
Correct |
23 ms |
28496 KB |
Output is correct |
| 6 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 7 |
Correct |
33 ms |
30848 KB |
Output is correct |
| 8 |
Correct |
34 ms |
30848 KB |
Output is correct |
| 9 |
Correct |
33 ms |
30848 KB |
Output is correct |
| 10 |
Correct |
33 ms |
30840 KB |
Output is correct |
| 11 |
Correct |
33 ms |
30968 KB |
Output is correct |
| 12 |
Runtime error |
62 ms |
58488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
147 ms |
76092 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 |
147 ms |
76092 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 |
28544 KB |
Output is correct |
| 3 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 5 |
Correct |
23 ms |
28496 KB |
Output is correct |
| 6 |
Correct |
21 ms |
28544 KB |
Output is correct |
| 7 |
Correct |
33 ms |
30848 KB |
Output is correct |
| 8 |
Correct |
34 ms |
30848 KB |
Output is correct |
| 9 |
Correct |
33 ms |
30848 KB |
Output is correct |
| 10 |
Correct |
33 ms |
30840 KB |
Output is correct |
| 11 |
Correct |
33 ms |
30968 KB |
Output is correct |
| 12 |
Runtime error |
62 ms |
58488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Halted |
0 ms |
0 KB |
- |
