Submission #7529

#	Time	Username	Problem	Language	Result	Execution time	Memory
7529		qja0950	Wall (IOI14_wall)	C++98	100 / 100	2340 ms	141720 KiB

wall

#include "wall.h"
#include <stdio.h>

#define INF 2100000000

struct NODE{
	int min, max;
	NODE *left, *right;
	NODE(int a, int b) {
		NODE::min  = a;
		NODE::max  = b;
		NODE::left = NULL;
		NODE::right= NULL;
	}
};

void Upload(NODE *node, int op, int h) {
	if(op == 1) {
		if(node->min < h) node->min = h;
		if(node->max < h) node->max = h;
	}
	if(op == 2) {
		if(node->min > h) node->min = h;
		if(node->max > h) node->max = h;
	}
	return;
}

int *Final;
void Change(NODE *now, int a, int b, int x, int y, int op, int h) {
	if(b<x || y<a) return;
	if(x<=a && b<=y) {
		Final[a] = now->min;
		Upload(now, op, h);
		return;
	}
	if(now->left == NULL) {
		now->left = new NODE(0, INF);
		now->right= new NODE(0, INF);
	}
	Upload(now->left , 1, now->min);
	Upload(now->left , 2, now->max);
	Upload(now->right, 1, now->min);
	Upload(now->right, 2, now->max);
	now->min = 0;
	now->max = INF;

	int m = (a+b)/2;
	Change(now->left	, a		, m, x, y, op, h);
	Change(now->right	, m+1	, b, x, y, op, h);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

	NODE *root = new NODE(0, 0);
	Final = finalHeight;

	for(int i=0; i<k; i++)
		Change(root, 0, n-1, left[i], right[i], op[i], height[i]);
	for(int i=0; i<n; i++)
		Change(root, 0, n-1, i, i, 2, INF);
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39