oj.uz

Submission #31200

# Submission time Handle Problem Language Result Execution time Memory
31200 2017-08-13T10:16:00 Z 14kg Wall (IOI14_wall) C++11
100 / 100
 1183 ms 141760 KB 
#include "wall.h"
#define N 2000001
#define max2(x,y) (x>y?x:y)
#define min2(x,y) (x<y?x:y)

struct WALL{
	int op, h;
} Tree[N * 4][2], NONO;
int n, nn, m;

WALL make_WALL(int op, int h)
{
	WALL temp;
	temp.op = op, temp.h = h;
	return temp;
}
void g(int lev, WALL num)
{
	if (num.op == -1) return;
	if (Tree[lev][0].op == -1){ Tree[lev][0] = num; return; }
	if (Tree[lev][1].op == -1){ Tree[lev][1] = num; return; }

	if (Tree[lev][0].op == Tree[lev][1].op)
	{
		if (Tree[lev][0].op == 1) Tree[lev][0].h = max2(Tree[lev][0].h, Tree[lev][1].h);
		else Tree[lev][0].h = min2(Tree[lev][0].h, Tree[lev][1].h);
		Tree[lev][1] = num; return;
	}
	if (Tree[lev][1].op == num.op)
	{
		if (num.op == 1) Tree[lev][1].h = max2(Tree[lev][1].h, num.h);
		else Tree[lev][1].h = min2(Tree[lev][1].h, num.h);
		return;
	}

	if (Tree[lev][1].op == 1)
	{
		if (Tree[lev][1].h > Tree[lev][0].h)
		{
			if (num.h < Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
			return;
		}
		if (num.h < Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
	}
	else
	{
		if (Tree[lev][0].h>Tree[lev][1].h)
		{
			if (num.h>Tree[lev][1].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
			return;
		}
		if (num.h > Tree[lev][0].h) Tree[lev][0] = Tree[lev][1], Tree[lev][1] = num;
	}
}
void Push(int lev, int l, int r, int x, int y, WALL num)
{
	int mid = (l + r) / 2;
	if (r < x || y < l) return;
	if (x <= l && r <= y){ g(lev, num); return; }

	g(lev * 2, Tree[lev][0]), g(lev * 2, Tree[lev][1]);
	g(lev * 2 + 1, Tree[lev][0]), g(lev * 2 + 1, Tree[lev][1]);
	Tree[lev][0] = Tree[lev][1] = NONO;

	Push(lev * 2, l, mid, x, y, num), Push(lev * 2 + 1, mid + 1, r, x, y, num);
}
int get_h(int lev, int h)
{
	if (lev == 0) return h;

	if (Tree[lev][0].op == 1) h = max2(h, Tree[lev][0].h);
	if (Tree[lev][0].op == 2) h = min2(h, Tree[lev][0].h);
	if (Tree[lev][1].op == 1) h = max2(h, Tree[lev][1].h);
	if (Tree[lev][1].op == 2) h = min2(h, Tree[lev][1].h);
	return get_h(lev / 2, h);
}
void buildWall(int _n, int _m, int _in1[], int _in2[], int _in3[], int _in4[], int out[]){
	WALL temp;
	int x, y;

	n=_n, m=_m, NONO = make_WALL(-1, -1);
	for (nn = 1; nn < n; nn *= 2);
	for (int i = 1; i < nn * 2; i++) Tree[i][0] = Tree[i][1] = NONO;

	for (int i = 1; i <= m; i++){
        temp.op=_in1[i-1], x=_in2[i-1], y=_in3[i-1], temp.h=_in4[i-1];
		x++, y++, Push(1, 1, nn, x, y, temp);
	}
	for (int i = 1; i <= n; i++) out[i-1]=get_h(nn + i - 1, 0);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 126120 KB Output is correct
2 Correct 0 ms 126120 KB Output is correct
3 Correct 0 ms 126120 KB Output is correct
4 Correct 6 ms 126120 KB Output is correct
5 Correct 6 ms 126120 KB Output is correct
6 Correct 6 ms 126120 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 126120 KB Output is correct
2 Correct 209 ms 133944 KB Output is correct
3 Correct 309 ms 129368 KB Output is correct
4 Correct 1063 ms 134336 KB Output is correct
5 Correct 389 ms 134336 KB Output is correct
6 Correct 446 ms 134336 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 126120 KB Output is correct
2 Correct 0 ms 126120 KB Output is correct
3 Correct 0 ms 126120 KB Output is correct
4 Correct 9 ms 126120 KB Output is correct
5 Correct 6 ms 126120 KB Output is correct
6 Correct 6 ms 126120 KB Output is correct
7 Correct 0 ms 126120 KB Output is correct
8 Correct 189 ms 133944 KB Output is correct
9 Correct 346 ms 129368 KB Output is correct
10 Correct 969 ms 134336 KB Output is correct
11 Correct 443 ms 134336 KB Output is correct
12 Correct 439 ms 134336 KB Output is correct
13 Correct 0 ms 126120 KB Output is correct
14 Correct 163 ms 133944 KB Output is correct
15 Correct 49 ms 126608 KB Output is correct
16 Correct 1033 ms 134336 KB Output is correct
17 Correct 426 ms 134336 KB Output is correct
18 Correct 413 ms 134336 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 126120 KB Output is correct
2 Correct 0 ms 126120 KB Output is correct
3 Correct 0 ms 126120 KB Output is correct
4 Correct 13 ms 126120 KB Output is correct
5 Correct 6 ms 126120 KB Output is correct
6 Correct 6 ms 126120 KB Output is correct
7 Correct 0 ms 126120 KB Output is correct
8 Correct 193 ms 133944 KB Output is correct
9 Correct 306 ms 129368 KB Output is correct
10 Correct 819 ms 134336 KB Output is correct
11 Correct 366 ms 134336 KB Output is correct
12 Correct 389 ms 134336 KB Output is correct
13 Correct 0 ms 126120 KB Output is correct
14 Correct 213 ms 133944 KB Output is correct
15 Correct 66 ms 126608 KB Output is correct
16 Correct 1183 ms 134336 KB Output is correct
17 Correct 436 ms 134336 KB Output is correct
18 Correct 416 ms 134336 KB Output is correct
19 Correct 969 ms 141760 KB Output is correct
20 Correct 1049 ms 141760 KB Output is correct
21 Correct 1002 ms 141760 KB Output is correct
22 Correct 1016 ms 141760 KB Output is correct
23 Correct 966 ms 141760 KB Output is correct
24 Correct 989 ms 141760 KB Output is correct
25 Correct 933 ms 141760 KB Output is correct
26 Correct 956 ms 141760 KB Output is correct
27 Correct 926 ms 141760 KB Output is correct
28 Correct 1099 ms 141760 KB Output is correct
29 Correct 1036 ms 141760 KB Output is correct
30 Correct 986 ms 141760 KB Output is correct