#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=2e5+5;
const ll N=2e5+5;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
struct node{
ll al,ar,bl,br,cl,cr;
node *son[2][2][2];
ll val;
}*rt=new node{0,INF,0,INF,0,INF,0,0,0,0,0,0,0,0,0};
ll get(node *nd){return (!nd?0:nd->val);}
void insert(node *nd,ll x,ll y,ll z){
//cout<<nd->al<<" "<<nd->ar<<"\n"<<nd->bl<<" "<<nd->br<<"\n"<<nd->cl<<" "<<nd->cr<<"\n\n";
if(nd->al==nd->ar-1&&nd->bl==nd->br-1&&nd->cl==nd->cr-1){
nd->val++;return;
}
ll midx=(nd->al+nd->ar)/2,midy=(nd->bl+nd->br)/2,midz=(nd->cl+nd->cr)/2;
if(!nd->son[(x>=midx)][(y>=midy)][(z>=midz)]){
nd->son[(x>=midx)][(y>=midy)][(z>=midz)]=new node{(x>=midx?midx:nd->al),(x>=midx?nd->ar:midx),(y>=midy?midy:nd->bl),(y>=midy?nd->br:midy),(z>=midz?midz:nd->cl),(z>=midz?nd->cr:midz),0,0,0,0,0,0,0,0,0};
}
insert(nd->son[(x>=midx)][(y>=midy)][(z>=midz)],x,y,z);
nd->val=0;
REP(i,2)REP(j,2)REP(k,2)nd->val+=get(nd->son[i][j][k]);
}
ll q(node *nd,ll xl,ll xr,ll yl,ll yr,ll zl,ll zr){
if(!nd)return 0;
if(nd->al>=xl&&nd->ar<=xr&&nd->bl>=yl&&nd->br<=yr&&nd->cl>=zl&&nd->cr<=zr)return nd->val;
if(nd->al>=xr||nd->ar<=xl||nd->bl>=yr||nd->br<=yl||nd->cl>=zr||nd->cr<=zl)return 0;
//ll midx=(nd->al+nd->ar)/2,midy=(nd->bl+nd->br)/2,midz=(nd->cl+nd->cr)/2,tmp=0;
ll tmp=0;
REP(i,2)REP(j,2)REP(k,2){
tmp+=q(nd->son[i][j][k],xl,xr,yl,yr,zl,zr);
}
return tmp;
}
ll n,Q,s,t,a,b,c;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>Q;
while(n--){
cin>>s>>t;
insert(rt,s,t,s+t);
}
while(Q--){
cin>>a>>b>>c;
cout<<q(rt,a,INF,b,INF,c,INF)<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3084 ms |
125560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3084 ms |
125560 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
