oj.uz

답안 #208915

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208915 2020-03-12T12:41:13 Z YJU Examination (JOI19_examination) C++14
0 / 100
 3000 ms 125560 KB 
#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;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3084 ms 125560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3084 ms 125560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 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 -