Submission #12193

# Submission time Handle Problem Language Result Execution time Memory
12193 2014-12-22T14:27:37 Z ho94949 Wall (IOI14_wall) C++
100 / 100
1180 ms 65880 KB
#include "wall.h"
#include <algorithm>
#define N 2097152
#define INF 987654321
int seg[2*N];
int minh[2*N];
int maxh[2*N];
void updatelazy(int ind){
	if(minh[ind]==-INF) return;
	seg[ind]=std::max(seg[ind],minh[ind]);
	seg[ind]=std::min(seg[ind],maxh[ind]);
	if(ind<N){
		if(maxh[2*ind]<minh[ind]) minh[2*ind]=maxh[2*ind]=minh[ind];
		if(maxh[ind]<minh[2*ind]) minh[2*ind]=maxh[2*ind]=maxh[ind];
		maxh[2*ind]=std::min(maxh[ind],maxh[2*ind]);
		minh[2*ind]=std::max(minh[ind],minh[2*ind]);
		if(maxh[2*ind+1]<minh[ind]) minh[2*ind+1]=maxh[2*ind+1]=minh[ind];
		if(maxh[ind]<minh[2*ind+1]) minh[2*ind+1]=maxh[2*ind+1]=maxh[ind];
		maxh[2*ind+1]=std::min(maxh[ind],maxh[2*ind+1]);
		minh[2*ind+1]=std::max(minh[ind],minh[2*ind+1]);
	}
	minh[ind]=-INF;
	maxh[ind]=INF;
	return;
}
void set(int ind,int indleft,int indright,int minv,int maxv,int left,int right){
	if(left<=indleft && indright <=right){
		if(maxh[ind]<minv) maxh[ind]=minh[ind]=minv;
		if(maxv<minh[ind]) minh[ind]=maxh[ind]=maxv;
		maxh[ind]=std::min(maxh[ind],maxv);
		minh[ind]=std::max(minh[ind],minv);
		updatelazy(ind);
		return;
	}
	updatelazy(ind);
	if(indright<left || right < indleft) return;
	if(ind<N){
		set(2*ind,indleft,(indleft+indright)/2,minv,maxv,left,right);
		set(2*ind+1,(indleft+indright)/2+1,indright,minv,maxv,left,right);
	}
	return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=1;i<2*N;i++) minh[i]=-INF,maxh[i]=INF;
	for(int i=0;i<k;i++){
		if(op[i]==2) set(1,0,N-1,0,height[i],left[i],right[i]);
		else set(1,0,N-1,height[i],INF,left[i],right[i]);
	}
	for(int i=1;i<N+n;i++) updatelazy(i);
	for(int i=0;i<n;i++) finalHeight[i]=seg[N+i];
	return;
}
# Verdict Execution time Memory Grader output
1 Correct 20 ms 50240 KB Output is correct
2 Correct 20 ms 50240 KB Output is correct
3 Correct 16 ms 50240 KB Output is correct
4 Correct 24 ms 50240 KB Output is correct
5 Correct 16 ms 50240 KB Output is correct
6 Correct 20 ms 50240 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 50240 KB Output is correct
2 Correct 392 ms 58064 KB Output is correct
3 Correct 388 ms 53488 KB Output is correct
4 Correct 1016 ms 58456 KB Output is correct
5 Correct 424 ms 58456 KB Output is correct
6 Correct 428 ms 58456 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 50240 KB Output is correct
2 Correct 16 ms 50240 KB Output is correct
3 Correct 16 ms 50240 KB Output is correct
4 Correct 28 ms 50240 KB Output is correct
5 Correct 16 ms 50240 KB Output is correct
6 Correct 16 ms 50240 KB Output is correct
7 Correct 12 ms 50240 KB Output is correct
8 Correct 376 ms 58064 KB Output is correct
9 Correct 388 ms 53488 KB Output is correct
10 Correct 1020 ms 58456 KB Output is correct
11 Correct 432 ms 58456 KB Output is correct
12 Correct 432 ms 58456 KB Output is correct
13 Correct 16 ms 50240 KB Output is correct
14 Correct 392 ms 58064 KB Output is correct
15 Correct 80 ms 50724 KB Output is correct
16 Correct 1164 ms 58456 KB Output is correct
17 Correct 432 ms 58456 KB Output is correct
18 Correct 428 ms 58456 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 50240 KB Output is correct
2 Correct 16 ms 50240 KB Output is correct
3 Correct 12 ms 50240 KB Output is correct
4 Correct 20 ms 50240 KB Output is correct
5 Correct 16 ms 50240 KB Output is correct
6 Correct 20 ms 50240 KB Output is correct
7 Correct 12 ms 50240 KB Output is correct
8 Correct 392 ms 58064 KB Output is correct
9 Correct 372 ms 53488 KB Output is correct
10 Correct 1020 ms 58456 KB Output is correct
11 Correct 440 ms 58456 KB Output is correct
12 Correct 424 ms 58456 KB Output is correct
13 Correct 20 ms 50240 KB Output is correct
14 Correct 392 ms 58064 KB Output is correct
15 Correct 80 ms 50724 KB Output is correct
16 Correct 1180 ms 58456 KB Output is correct
17 Correct 420 ms 58456 KB Output is correct
18 Correct 432 ms 58456 KB Output is correct
19 Correct 972 ms 65880 KB Output is correct
20 Correct 976 ms 65880 KB Output is correct
21 Correct 976 ms 65880 KB Output is correct
22 Correct 988 ms 65880 KB Output is correct
23 Correct 992 ms 65880 KB Output is correct
24 Correct 1004 ms 65880 KB Output is correct
25 Correct 972 ms 65880 KB Output is correct
26 Correct 976 ms 65880 KB Output is correct
27 Correct 1012 ms 65880 KB Output is correct
28 Correct 988 ms 65880 KB Output is correct
29 Correct 1008 ms 65880 KB Output is correct
30 Correct 972 ms 65880 KB Output is correct