oj.uz

답안 #12191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12191 2014-12-22T14:24:25 Z ho94949 벽 (IOI14_wall) C++
61 / 100
 1128 ms 41300 KB 
#include "wall.h"
#include <algorithm>
#define N 1048576
#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;
	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 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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 25664 KB Output is correct
2 Correct 4 ms 25664 KB Output is correct
3 Correct 12 ms 25664 KB Output is correct
4 Correct 16 ms 25664 KB Output is correct
5 Correct 16 ms 25664 KB Output is correct
6 Correct 12 ms 25664 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 25664 KB Output is correct
2 Correct 368 ms 33488 KB Output is correct
3 Correct 352 ms 28912 KB Output is correct
4 Correct 980 ms 33880 KB Output is correct
5 Correct 420 ms 33880 KB Output is correct
6 Correct 408 ms 33880 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 25664 KB Output is correct
2 Correct 12 ms 25664 KB Output is correct
3 Correct 12 ms 25664 KB Output is correct
4 Correct 12 ms 25664 KB Output is correct
5 Correct 12 ms 25664 KB Output is correct
6 Correct 16 ms 25664 KB Output is correct
7 Correct 4 ms 25664 KB Output is correct
8 Correct 364 ms 33488 KB Output is correct
9 Correct 352 ms 28912 KB Output is correct
10 Correct 988 ms 33880 KB Output is correct
11 Correct 408 ms 33880 KB Output is correct
12 Correct 412 ms 33880 KB Output is correct
13 Correct 12 ms 25664 KB Output is correct
14 Correct 376 ms 33488 KB Output is correct
15 Correct 68 ms 26148 KB Output is correct
16 Correct 1124 ms 33880 KB Output is correct
17 Correct 424 ms 33880 KB Output is correct
18 Correct 420 ms 33880 KB Output is correct

Subtask #4
0.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 25664 KB Output is correct
2 Correct 8 ms 25664 KB Output is correct
3 Correct 4 ms 25664 KB Output is correct
4 Correct 16 ms 25664 KB Output is correct
5 Correct 12 ms 25664 KB Output is correct
6 Correct 12 ms 25664 KB Output is correct
7 Correct 4 ms 25664 KB Output is correct
8 Correct 364 ms 33488 KB Output is correct
9 Correct 348 ms 28912 KB Output is correct
10 Correct 968 ms 33880 KB Output is correct
11 Correct 420 ms 33880 KB Output is correct
12 Correct 400 ms 33880 KB Output is correct
13 Correct 12 ms 25664 KB Output is correct
14 Correct 364 ms 33488 KB Output is correct
15 Correct 64 ms 26148 KB Output is correct
16 Correct 1128 ms 33880 KB Output is correct
17 Correct 412 ms 33880 KB Output is correct
18 Correct 408 ms 33880 KB Output is correct
19 Runtime error 460 ms 41300 KB Program hung waiting for input
20 Halted 0 ms 0 KB -