oj.uz

Submission #208907

# Submission time Handle Problem Language Result Execution time Memory
208907 2020-03-12T12:35:14 Z YJU Examination (JOI19_examination) C++14
0 / 100
 3000 ms 1048580 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF=2e9+1;
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;
	}
	long long 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;
}

Compilation message

examination.cpp: In function 'void insert(node*, ll, ll, ll)':
examination.cpp:31:61: warning: narrowing conversion of '((((long long int)x) >= midx) ? midx : ((long long int)nd->node::al))' from 'long long int' to 'll {aka int}' inside { } [-Wnarrowing]
   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};
                                                     ~~~~~~~~^~~~~~~~~~~~~
examination.cpp:31:83: warning: narrowing conversion of '((((long long int)x) >= midx) ? ((long long int)nd->node::ar) : midx)' from 'long long int' to 'll {aka int}' inside { } [-Wnarrowing]
   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};
                                                                           ~~~~~~~~^~~~~~~~~~~~~
examination.cpp:31:105: warning: narrowing conversion of '((((long long int)y) >= midy) ? midy : ((long long int)nd->node::bl))' from 'long long int' to 'll {aka int}' inside { } [-Wnarrowing]
   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};
                                                                                                 ~~~~~~~~^~~~~~~~~~~~~
examination.cpp:31:127: warning: narrowing conversion of '((((long long int)y) >= midy) ? ((long long int)nd->node::br) : midy)' from 'long long int' to 'll {aka int}' inside { } [-Wnarrowing]
   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};
                                                                                                                       ~~~~~~~~^~~~~~~~~~~~~
examination.cpp:31:149: warning: narrowing conversion of '((((long long int)z) >= midz) ? midz : ((long long int)nd->node::cl))' from 'long long int' to 'll {aka int}' inside { } [-Wnarrowing]
   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};
                                                                                                                                             ~~~~~~~~^~~~~~~~~~~~~
examination.cpp:31:171: warning: narrowing conversion of '((((long long int)z) >= midz) ? ((long long int)nd->node::cr) : midz)' from 'long long int' to 'll {aka int}' inside { } [-Wnarrowing]
   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};
                                                                                                                                                                   ~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Runtime error 826 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 108744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 108744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Runtime error 826 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -