#include "bits/stdc++.h"
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
using namespace std;
const int N=1e5+5;
struct query{
ll i,x,y,z;
bool operator<(const query &o)const{return x>o.x;}
};
struct fenwick{
vector<ll>v,fw;
void build(){
fw.resize(v.size()+1,0);
}
void upd(ll i){
i = upper_bound(all(v),i)-v.begin();
for(;i<sz(fw);i+=i&-i)fw[i]++;
}
int qr(ll i,int res=0){
i = upper_bound(all(v),i)-v.begin();
for(;i;i-=i&-i)res+=fw[i];
return res;
}
}t[4*N];
pii b[N];
ll c[N];
void build(int i,int l,int r){
if(l==r){
t[i].v.pb(b[l].s+b[l].f);t[i].build();
return;
}int m=(l+r)>>1;
build(2*i,l,m);build(2*i+1,m+1,r);
int li=0,ri=0;
while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
if(t[2*i].v[li]<t[2*i+1].v[ri])t[i].v.pb(t[2*i].v[li++]);
else t[i].v.pb(t[2*i+1].v[ri++]);
}while(li<t[2*i].v.size())t[i].v.pb(t[2*i].v[li++]);
while(ri<t[2*i+1].v.size())t[i].v.pb(t[2*i+1].v[ri++]);
t[i].build();
}
void upd(int i,int l,int r,int idx,ll v){
if(r<idx||l>idx)return;
if(l==r)return void(t[i].upd(v));
int m=(l+r)>>1;
upd(2*i,l,m,idx,v);upd(2*i+1,m+1,r,idx,v);
t[i].upd(v);
}
int qr(int i,int l,int r,int tl,int tr,ll v){
if(r<tl||l>tr)return 0;
if(r<=tr&&l>=tl){
return t[i].qr(v);
}int m=(l+r)>>1;
return qr(2*i,l,m,tl,tr,v)+qr(2*i+1,m+1,r,tl,tr,v);
}
map<pii,ll>mp;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++)cin>>b[i].f>>b[i].s,c[i]=b[i].s,mp[{b[i].f,b[i].s}]=b[i].f+b[i].s;
sort(b+1,b+1+n);build(1,1,n);sort(c+1,c+n+1);
query qq[q];
for(int i=0;i<q;i++)cin>>qq[i].x>>qq[i].y>>qq[i].z,qq[i].i=i;
sort(qq,qq+q);
int ans[q];int j=n;
for(int i=0;i<q;i++){
while(j>0&&b[j].f>=qq[i].x){
int id=lower_bound(c+1,c+n+1,b[j].s)-c;
upd(1,1,n,id,mp[{b[j].f,b[j].s}]);j--;
}int id=lower_bound(c+1,c+1+n,qq[i].y)-c;
ans[qq[i].i] = qr(1,1,n,id,n,1e16)-qr(1,1,n,id,n,qq[i].z-1);
}for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
}
Compilation message
examination.cpp: In function 'void build(int, int, int)':
examination.cpp:39:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
| ~~^~~~~~~~~~~~~~~~
examination.cpp:39:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
| ~~^~~~~~~~~~~~~~~~~~
examination.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | }while(li<t[2*i].v.size())t[i].v.pb(t[2*i].v[li++]);
| ~~^~~~~~~~~~~~~~~~
examination.cpp:43:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | while(ri<t[2*i+1].v.size())t[i].v.pb(t[2*i+1].v[ri++]);
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3031 ms |
21336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3006 ms |
70176 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3006 ms |
70176 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3031 ms |
21336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
