oj.uz

답안 #15784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15784 2015-07-26T10:57:02 Z myungwoo 벽 (IOI14_wall) C++14
0 / 100
 717 ms 15624 KB 
#include <stdlib.h>
#include <algorithm>
using namespace std;

static int N,K,*H;

struct NODE{
	NODE(int h=0): mini(h),maxi(h),left(NULL),right(NULL) {}
	int mini,maxi;
	NODE *left,*right;
};

void dfs(NODE *now,int s,int e,int l,int r,int mini,int maxi,int op,int h)
{
	if (mini <= now->mini && now->maxi <= maxi);
	else if (now->mini < mini && maxi < now->maxi) now->mini = mini, now->maxi = maxi;
	else if (maxi < now->mini) now->mini = now->maxi = maxi;
	else if (now->maxi < mini) now->mini = now->maxi = mini;
	else if (mini > now->mini) now->mini = mini;
	else if (maxi < now->maxi) now->maxi = maxi;
	mini = now->mini; maxi = now->maxi;
	if (e < l || s > r) return;
	if (l <= s && e <= r){
		if (op == 1){   // add
			if (now->mini < h) now->mini = h;
			if (now->maxi < h) now->maxi = h;
		}else{          // remove
			if (now->maxi > h) now->maxi = h;
			if (now->mini > h) now->mini = h;
		}
		return;
	}
	int m = (s+e)>>1;
	if (now->left == NULL){
		now->left = new NODE(now->mini);
		now->right = new NODE(now->mini);
	}
	dfs(now->left,s,m,l,r,mini,maxi,op,h);
	dfs(now->right,m+1,e,l,r,mini,maxi,op,h);
	now->mini = min(now->left->mini,now->right->mini);
	now->maxi = max(now->left->maxi,now->right->maxi);
}

void cdfs(NODE *now,int s,int e,int mini,int maxi)
{
	if (mini <= now->mini && now->maxi <= maxi);
	else if (now->mini < mini && maxi < now->maxi) now->mini = mini, now->maxi = maxi;
	else if (maxi < now->mini) now->mini = now->maxi = maxi;
	else if (now->maxi < mini) now->mini = now->maxi = mini;
	else if (mini > now->mini) now->mini = mini;
	else if (maxi < now->maxi) now->maxi = maxi;
	mini = now->mini; maxi = now->maxi;
	if (s == e){
		H[s] = mini;
		return;
	}
	int m = (s+e)>>1;
	cdfs(now->left,s,m,mini,maxi);
	cdfs(now->right,m+1,e,mini,maxi);
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
	int i;
	NODE *root = new NODE();
	N = n, K = k;
	for (i=0;i<K;i++){
		dfs(root,0,N-1,left[i],right[i],0,1e9,op[i],height[i]);
	}
	H = finalHeight;
	cdfs(root,0,N-1,0,1e9);
}

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Runtime error 8 ms 1732 KB SIGSEGV Segmentation fault
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 200 ms 9032 KB Output is correct
3 Correct 231 ms 5644 KB Output is correct
4 Runtime error 717 ms 15624 KB SIGSEGV Segmentation fault
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 3 ms 1208 KB Output is correct
4 Runtime error 5 ms 1732 KB SIGSEGV Segmentation fault
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 3 ms 1208 KB Output is correct
3 Correct 2 ms 1208 KB Output is correct
4 Runtime error 9 ms 1732 KB SIGSEGV Segmentation fault
5 Halted 0 ms 0 KB -