oj.uz

답안 #12192

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12192 2014-12-22T14:25:59 Z ho94949 벽 (IOI14_wall) C++
61 / 100
 1148 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){
		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;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 25664 KB Output is correct
2 Correct 12 ms 25664 KB Output is correct
3 Correct 16 ms 25664 KB Output is correct
4 Correct 8 ms 25664 KB Output is correct
5 Correct 12 ms 25664 KB Output is correct
6 Correct 8 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 348 ms 28912 KB Output is correct
4 Correct 972 ms 33880 KB Output is correct
5 Correct 428 ms 33880 KB Output is correct
6 Correct 400 ms 33880 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 25664 KB Output is correct
2 Correct 8 ms 25664 KB Output is correct
3 Correct 12 ms 25664 KB Output is correct
4 Correct 24 ms 25664 KB Output is correct
5 Correct 16 ms 25664 KB Output is correct
6 Correct 8 ms 25664 KB Output is correct
7 Correct 4 ms 25664 KB Output is correct
8 Correct 360 ms 33488 KB Output is correct
9 Correct 352 ms 28912 KB Output is correct
10 Correct 972 ms 33880 KB Output is correct
11 Correct 432 ms 33880 KB Output is correct
12 Correct 404 ms 33880 KB Output is correct
13 Correct 4 ms 25664 KB Output is correct
14 Correct 372 ms 33488 KB Output is correct
15 Correct 64 ms 26148 KB Output is correct
16 Correct 1148 ms 33880 KB Output is correct
17 Correct 428 ms 33880 KB Output is correct
18 Correct 424 ms 33880 KB Output is correct

Subtask #4
0.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 25664 KB Output is correct
2 Correct 8 ms 25664 KB Output is correct
3 Correct 16 ms 25664 KB Output is correct
4 Correct 20 ms 25664 KB Output is correct
5 Correct 8 ms 25664 KB Output is correct
6 Correct 16 ms 25664 KB Output is correct
7 Correct 8 ms 25664 KB Output is correct
8 Correct 384 ms 33488 KB Output is correct
9 Correct 356 ms 28912 KB Output is correct
10 Correct 972 ms 33880 KB Output is correct
11 Correct 412 ms 33880 KB Output is correct
12 Correct 416 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 1124 ms 33880 KB Output is correct
17 Correct 416 ms 33880 KB Output is correct
18 Correct 400 ms 33880 KB Output is correct
19 Runtime error 468 ms 41300 KB Program hung waiting for input
20 Halted 0 ms 0 KB -