Submission #15784

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15784	2015-07-26T10:57:02 Z	myungwoo	Wall (IOI14_wall)	C++14	0 / 100	717 ms	15624 KB

wall

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-