oj.uz

답안 #208904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208904 2020-03-12T12:33:36 Z YJU Examination (JOI19_examination) C++14
2 / 100
 3000 ms 123896 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long 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;
	}
	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;
	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 'll q(node*, ll, ll, ll, ll, ll, ll)':
examination.cpp:42:5: warning: unused variable 'midx' [-Wunused-variable]
  ll midx=(nd->al+nd->ar)/2,midy=(nd->bl+nd->br)/2,midz=(nd->cl+nd->cr)/2,tmp=0;
     ^~~~
examination.cpp:42:28: warning: unused variable 'midy' [-Wunused-variable]
  ll midx=(nd->al+nd->ar)/2,midy=(nd->bl+nd->br)/2,midz=(nd->cl+nd->cr)/2,tmp=0;
                            ^~~~
examination.cpp:42:51: warning: unused variable 'midz' [-Wunused-variable]
  ll midx=(nd->al+nd->ar)/2,midy=(nd->bl+nd->br)/2,midz=(nd->cl+nd->cr)/2,tmp=0;
                                                   ^~~~

Subtask #1
2.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 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 52 ms 10104 KB Output is correct
8 Correct 54 ms 10104 KB Output is correct
9 Correct 56 ms 10104 KB Output is correct
10 Correct 2439 ms 7928 KB Output is correct
11 Correct 2549 ms 7928 KB Output is correct
12 Correct 14 ms 376 KB Output is correct
13 Correct 71 ms 10104 KB Output is correct
14 Correct 70 ms 10104 KB Output is correct
15 Correct 69 ms 10104 KB Output is correct
16 Correct 2108 ms 7928 KB Output is correct
17 Correct 1286 ms 7928 KB Output is correct
18 Correct 11 ms 376 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3064 ms 123896 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 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 52 ms 10104 KB Output is correct
8 Correct 54 ms 10104 KB Output is correct
9 Correct 56 ms 10104 KB Output is correct
10 Correct 2439 ms 7928 KB Output is correct
11 Correct 2549 ms 7928 KB Output is correct
12 Correct 14 ms 376 KB Output is correct
13 Correct 71 ms 10104 KB Output is correct
14 Correct 70 ms 10104 KB Output is correct
15 Correct 69 ms 10104 KB Output is correct
16 Correct 2108 ms 7928 KB Output is correct
17 Correct 1286 ms 7928 KB Output is correct
18 Correct 11 ms 376 KB Output is correct
19 Execution timed out 3064 ms 123896 KB Time limit exceeded
20 Halted 0 ms 0 KB -