oj.uz

Submission #12190

# Submission time Handle Problem Language Result Execution time Memory
12190 2014-12-22T14:20:56 Z ho94949 Wall (IOI14_wall) C++
0 / 100
 196 ms 8912 KB 
#include "wall.h"
#include <algorithm>
#define N 16
#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){
		// [minh[2*ind],maxh[2*ind]]
		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){
	//fprintf(stderr,"%d %d %d %d %d %d %d\n",ind,indleft,indright,minv,maxv,left,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;
	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 j=1;j<2*N;j++) printf("%d: %d %d %d\n",j, seg[j],minh[j],maxh[j]);
		//puts("=====");
	}
	for(int i=1;i<N+n;i++) updatelazy(i);
	for(int i=0;i<n;i++) finalHeight[i]=seg[N+i];
	return;
}

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Incorrect 0 ms 1088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 196 ms 8912 KB Output is correct
3 Runtime error 80 ms 4332 KB SIGSEGV Segmentation fault
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Incorrect 0 ms 1088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Incorrect 0 ms 1088 KB Output isn't correct
4 Halted 0 ms 0 KB -