oj.uz

답안 #18099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18099 2016-01-20T07:50:37 Z comet 벽 (IOI14_wall) C++
100 / 100
 1743 ms 55784 KB 
#include "wall.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define LL 2*k+1
#define RR 2*k+2

int lo[5000010],hi[5000010];

void up(int k){
	lo[k]=min(lo[LL],lo[RR]);
	hi[k]=max(hi[LL],hi[RR]);
}

void down(int k){
	lo[LL]=max(lo[LL],lo[k]);
	hi[LL]=max(hi[LL],lo[LL]);
	lo[RR]=max(lo[RR],lo[k]);
	hi[RR]=max(hi[RR],lo[RR]);

	hi[LL]=min(hi[LL],hi[k]);
	lo[LL]=min(lo[LL],hi[LL]);
	hi[RR]=min(hi[RR],hi[k]);
	lo[RR]=min(lo[RR],hi[RR]);
}

void update(int s,int e,int L,int R,int D,int c,int k){
	if(e<L||s>R)return;
	if(L<=s&&e<=R){
		if(D==1){
			lo[k]=max(lo[k],c);
			hi[k]=max(hi[k],lo[k]);
		}
		if(D==2){
			hi[k]=min(hi[k],c);
			lo[k]=min(lo[k],hi[k]);
		}
		return;
	}
	down(k);
	int mid=(s+e)/2;
	update(s,mid,L,R,D,c,LL);
	update(mid+1,e,L,R,D,c,RR);
	up(k);
}

int query(int s,int e,int x,int k){
	if(s==e){
		return lo[k];
	}
	down(k);
	int mid=(s+e)/2;
	if(x<=mid)return query(s,mid,x,LL);
	return query(mid+1,e,x,RR);
}

#undef LL
#undef RR

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	for(int i=0;i<k;i++){
		update(0,n-1,left[i],right[i],op[i],height[i],0);
	}
	for(int i=0;i<n;i++){
		finalHeight[i]=query(0,n-1,i,0);
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 40144 KB Output is correct
2 Correct 0 ms 40144 KB Output is correct
3 Correct 0 ms 40144 KB Output is correct
4 Correct 9 ms 40144 KB Output is correct
5 Correct 8 ms 40144 KB Output is correct
6 Correct 8 ms 40144 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 40144 KB Output is correct
2 Correct 171 ms 47968 KB Output is correct
3 Correct 268 ms 43392 KB Output is correct
4 Correct 801 ms 48360 KB Output is correct
5 Correct 340 ms 48360 KB Output is correct
6 Correct 511 ms 48360 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 40144 KB Output is correct
2 Correct 0 ms 40144 KB Output is correct
3 Correct 0 ms 40144 KB Output is correct
4 Correct 10 ms 40144 KB Output is correct
5 Correct 8 ms 40144 KB Output is correct
6 Correct 8 ms 40144 KB Output is correct
7 Correct 0 ms 40144 KB Output is correct
8 Correct 178 ms 47968 KB Output is correct
9 Correct 266 ms 43392 KB Output is correct
10 Correct 768 ms 48360 KB Output is correct
11 Correct 533 ms 48360 KB Output is correct
12 Correct 500 ms 48360 KB Output is correct
13 Correct 0 ms 40144 KB Output is correct
14 Correct 191 ms 47968 KB Output is correct
15 Correct 44 ms 40628 KB Output is correct
16 Correct 791 ms 48360 KB Output is correct
17 Correct 421 ms 48360 KB Output is correct
18 Correct 523 ms 48360 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 40144 KB Output is correct
2 Correct 2 ms 40144 KB Output is correct
3 Correct 0 ms 40144 KB Output is correct
4 Correct 7 ms 40144 KB Output is correct
5 Correct 8 ms 40144 KB Output is correct
6 Correct 5 ms 40144 KB Output is correct
7 Correct 0 ms 40144 KB Output is correct
8 Correct 158 ms 47968 KB Output is correct
9 Correct 272 ms 43392 KB Output is correct
10 Correct 775 ms 48360 KB Output is correct
11 Correct 559 ms 48360 KB Output is correct
12 Correct 556 ms 48360 KB Output is correct
13 Correct 0 ms 40144 KB Output is correct
14 Correct 211 ms 47968 KB Output is correct
15 Correct 47 ms 40628 KB Output is correct
16 Correct 806 ms 48360 KB Output is correct
17 Correct 534 ms 48360 KB Output is correct
18 Correct 511 ms 48360 KB Output is correct
19 Correct 1672 ms 55784 KB Output is correct
20 Correct 1739 ms 55784 KB Output is correct
21 Correct 1743 ms 55784 KB Output is correct
22 Correct 1686 ms 55784 KB Output is correct
23 Correct 1668 ms 55784 KB Output is correct
24 Correct 1646 ms 55784 KB Output is correct
25 Correct 1628 ms 55784 KB Output is correct
26 Correct 1656 ms 55784 KB Output is correct
27 Correct 1666 ms 55784 KB Output is correct
28 Correct 1694 ms 55784 KB Output is correct
29 Correct 1570 ms 55784 KB Output is correct
30 Correct 1660 ms 55784 KB Output is correct