#include <bits/stdc++.h>
using namespace std;
using nagai = long long;
#define sz(x) int((x).size())
int act=0;
struct fen{
vector<int>v;
vector<int>t;
void add1(int x,int y){
for(;x<t.size();x+=x&-x)
t[x]+=y;
}
int get(int x){
if(act<2)return 0;
int ans=0;
for(;x;x-=x&-x)
ans+=t[x];
return ans;
}
void add(int x,int y){
if(act<2)
return v.push_back(x);
x=lower_bound(v.begin(),v.end(),x)-v.begin();
add1(x+1,y);
}
int get(int l,int r){
l=lower_bound(v.begin(),v.end(),l)-v.begin();
r=lower_bound(v.begin(),v.end(),r)-v.begin();
return get(r)-get(l);
}
};
const int N=100100;
//const int oo=0x3f3f3f3f;
struct FEN{
fen kek[N];
vector<int>v;
void add1(int x,int y,int z){
for(;x<N;x+=x&-x)
kek[x].add(y,z);
}
int get(int x,int y1,int y2){
if(act<2)return 0;
int ans=0;
for(;x;x-=x&-x)
ans+=kek[x].get(y1,y2);
return ans;
}
void add(int x,int y,int z){
if(act==0)
return v.push_back(x);
x=lower_bound(v.begin(),v.end(),x)-v.begin();
add1(x+1,y,z);
}
int get(int x1,int x2,int y1,int y2){
x1=lower_bound(v.begin(),v.end(),x1)-v.begin();
x2=lower_bound(v.begin(),v.end(),x2)-v.begin();
return get(x2,y1,y2)-get(x1,y1,y2);
}
void init(){
if(act==0){
sort(v.begin(),v.end());
}
else{
for(int i=0;i<N;++i){
kek[i].v.push_back(1e9);
kek[i].v.push_back(1e9);
sort(kek[i].v.begin(),kek[i].v.end());
kek[i].t.resize(kek[i].v.size()+1);
}
}
++act;
}
} F;
int n,q;
int xs[N],ys[N];
int as[N],bs[N],cs[N];
struct ev{
int x,y1,y2,z1,z2,id;
bool operator <(ev o)const {
if(x!=o.x)
return x>o.x;
return id<o.id;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
for(int i=0;i<n;++i){
cin>>xs[i]>>ys[i];
}
for(int i=0;i<q;++i){
cin>>as[i]>>bs[i]>>cs[i];
}
vector<int>ans(q);
for(int i=0;i<3;++i){
vector<ev>evs;
for(int i=0;i<n;++i)
evs.push_back({xs[i],ys[i],ys[i],xs[i]+ys[i],xs[i]+ys[i],-1});
for(int i=0;i<q;++i){
evs.push_back({as[i],bs[i],N-3,cs[i],N-3,i});
}
sort(evs.begin(),evs.end());
for(auto e:evs){
if(e.id==-1){
F.add(e.y1,e.z1,1);
continue;
}
ans[e.id]=F.get(e.y1,e.y2,e.z1,e.z2);
}
F.init();
}
for(int i=0;i<q;++i)
cout<<ans[i]<<'\n';
return 0;
}
Compilation message
examination.cpp: In member function 'void fen::add1(int, int)':
examination.cpp:13:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;x<t.size();x+=x&-x)
~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
33 ms |
11392 KB |
Output is correct |
| 2 |
Correct |
34 ms |
11384 KB |
Output is correct |
| 3 |
Correct |
32 ms |
11392 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
11392 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
642 ms |
32736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
642 ms |
32736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
33 ms |
11392 KB |
Output is correct |
| 2 |
Correct |
34 ms |
11384 KB |
Output is correct |
| 3 |
Correct |
32 ms |
11392 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
11392 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
