#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FORi(i,a,b) for(ll i=((ll)a);i<(ll)b;i++)
#define FOR(i,n) FORi(i,0,n)
#define FOA(v,a) for(auto v : a)
#define INF 0
#define INF2 100000
#define MID ((l+r)/2)
typedef pair<int, int> ii;
#define F first
#define S second
struct seg{
seg* L=NULL, *R=NULL;
int val=0;
int pos=-1;
void push(int l, int r){
if(pos!=-1){
if(pos<=MID){
L = new seg;
L->val = 1;
L->pos = pos;
}
else{
R = new seg;
R->val = 1;
R->pos = pos;
}
pos = -1;
}
}
void update(int x, int l=0, int r=INF2){
if(l==r && l==x) val++;
else if(l==r) return;
else{
val++;
if(!L && !R && pos==-1){
pos = x;
return;
}
push(l,r);
if(x<=MID){
if(!L) L = new seg;
L->update(x,l,MID);
}
else{
if(!R) R = new seg;
R->update(x,MID+1,r);
}
}
}
int query(int rl, int rr, int l=0, int r=INF2){
if(rl<=l && r<=rr) return val;
else if(rr<l || r<rl) return 0;
else{
push(l,r);
int ans=0;
if(L) ans+=L->query(rl,rr,l,MID);
if(R) ans+=R->query(rl,rr,MID+1,r);
return ans;
}
}
};
struct seg2{
seg2* L=NULL, *R=NULL;
seg val;
int pos=-1;
void push(int l, int r){
if(pos!=-1){
if(pos<=MID){
L = new seg2;
L->val = val;
L->pos = pos;
}
else{
R = new seg2;
R->val = val;
R->pos = pos;
}
pos = -1;
}
}
void update(ii x, int l=0, int r=INF2){
if(l==r && l==x.F) val.update(x.S);
else if(l==r) return;
else{
if(!L && !R && pos==-1){
val.update(x.S);
pos = x.F;
return;
}
push(l,r);
if(x.F<=MID){
if(!L) L = new seg2;
L->update(x,l,MID);
}
else{
if(!R) R = new seg2;
R->update(x,MID+1,r);
}
val.update(x.S);
}
}
int query(ii rl, ii rr, int l=0, int r=INF2){
if(rl.F<=l && r<=rr.F) return val.query(rl.S, rr.S);
else if(rr.F<l || r<rl.F) return 0;
else{
push(l,r);
int ans=0;
if(L) ans+=L->query(rl,rr,l,MID);
if(R) ans+=R->query(rl,rr,MID+1,r);
return ans;
}
}
};
struct seg3{
seg3* L=NULL, *R=NULL;
seg2 val;
void update(pair<ii,int> x, int l=0, int r=2*INF){
if(l==r && l==x.S) val.update(x.F);
else if(l==r) return;
else{
if(x.S<=MID){
if(!L) L = new seg3;
L->update(x,l,MID);
}
else{
if(!R) R = new seg3;
R->update(x,MID+1,r);
}
val.update(x.F);
}
}
int query(pair<ii,int> rl, pair<ii,int> rr, int l=0, int r=2*INF){
if(rl.S<=l && r<=rr.S) return val.query(rl.F, rr.F);
else if(rr.S<l || r<rl.S) return 0;
else{
int ans=0;
if(L) ans+=L->query(rl,rr,l,MID);
if(R) ans+=R->query(rl,rr,MID+1,r);
return ans;
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin>>n>>q;
seg3 s;
vector<pair<ii,int> > qq;
vector<pair<ii,int> > dd;
FOR(i,n){
int a, b;
cin>>a>>b;
dd.push_back({{a,b},a+b});
}
while(q--){
int a, b, c;
cin>>a>>b>>c;
qq.push_back({{a,b},c});
}
set<int> p1, p2;
FOA(v,dd) p1.insert(v.F.F);
FOA(v,dd) p2.insert(v.F.S);
FOA(v,qq) p1.insert(v.F.F);
FOA(v,qq) p2.insert(v.F.S);
map<int, int> m1, m2;
int cnt=1;
FOA(v,p1) m1[v] = cnt++;
cnt=1;
FOA(v,p2) m2[v] = cnt++;
FOA(v,dd) s.update({{m1[v.F.F], m2[v.F.S]},v.S});
FOA(v,qq){
cout<<s.query({{m1[v.F.F], m2[v.F.S]},v.S}, {{INF2, INF2}, 2*INF})<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
19056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
19056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
