oj.uz

Submission #861056

# Submission time Handle Problem Language Result Execution time Memory
861056 2023-10-15T08:15:23 Z MongHwa Wall (IOI14_wall) C++17
100 / 100
 755 ms 59340 KB 
#include <wall.h>
#include <vector>
#include <cmath>
using namespace std;

#define X first
#define Y second
#define INF 0x7f7f7f7f

int idx;

void init(vector<pair<int, int>>& lazy, int node, int start, int end)
{
	if(start == end)
		lazy[node] = {0, INF};
	else
	{
		init(lazy, node*2, start, (start+end)/2);
		init(lazy, node*2+1, (start+end)/2+1, end);
		lazy[node] = {0, INF};
	}
}

void update_lazy(vector<pair<int, int>>& lazy, int node, int start, int end)
{
	if(start != end)
	{
		lazy[node*2].X = max(lazy[node*2].X, lazy[node].X);
		lazy[node*2].Y = max(lazy[node*2].Y, lazy[node].X);
		lazy[node*2+1].X = max(lazy[node*2+1].X, lazy[node].X);
		lazy[node*2+1].Y = max(lazy[node*2+1].Y, lazy[node].X);

		lazy[node*2].X = min(lazy[node*2].X, lazy[node].Y);
		lazy[node*2].Y = min(lazy[node*2].Y, lazy[node].Y);
		lazy[node*2+1].X = min(lazy[node*2+1].X, lazy[node].Y);
		lazy[node*2+1].Y = min(lazy[node*2+1].Y, lazy[node].Y);

		lazy[node] = {0, INF};
	}
}

void update_range(vector<pair<int, int>>& lazy, int node, int start, int end, int left, int right, int type, int val)
{
	update_lazy(lazy, node, start, end);
	if(right < start || left > end)
		return;
	if(left <= start && end <= right)
	{
		if(type == 1)
		{
			lazy[node].X = max(lazy[node].X, val);
			lazy[node].Y = max(lazy[node].Y, val);
		}
		else if(type == 2)
		{
			lazy[node].X = min(lazy[node].X, val);
			lazy[node].Y = min(lazy[node].Y, val);
		}
		update_lazy(lazy, node, start, end);
		return;
	}

	update_range(lazy, node*2, start, (start+end)/2, left, right, type, val);
	update_range(lazy, node*2+1, (start+end)/2+1, end, left, right, type, val);
}

void ans(vector<pair<int, int>>& lazy, int result[], int node, int start, int end)
{
	update_lazy(lazy, node, start, end);
	if(start == end)
		result[idx++] = lazy[node].X;
	else
	{
		ans(lazy, result, node*2, start, (start+end)/2);
		ans(lazy, result, node*2+1, (start+end)/2+1, end);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	int h = (int)ceil(log2(n));
	int tree_size = (1<<(h+1));
	vector<pair<int, int>> lazy(tree_size);

	init(lazy, 1, 0, n-1);

	for(int i = 0; i < k; i++)
		update_range(lazy, 1, 0, n-1, left[i], right[i], op[i], height[i]);

	ans(lazy, finalHeight, 1, 0, n-1);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 99 ms 8092 KB Output is correct
3 Correct 189 ms 4176 KB Output is correct
4 Correct 498 ms 20164 KB Output is correct
5 Correct 294 ms 20796 KB Output is correct
6 Correct 305 ms 19032 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 856 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 101 ms 13960 KB Output is correct
9 Correct 168 ms 8024 KB Output is correct
10 Correct 503 ms 20188 KB Output is correct
11 Correct 314 ms 20712 KB Output is correct
12 Correct 288 ms 19284 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 102 ms 13904 KB Output is correct
15 Correct 27 ms 1884 KB Output is correct
16 Correct 483 ms 20128 KB Output is correct
17 Correct 292 ms 19508 KB Output is correct
18 Correct 295 ms 19592 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 688 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 856 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 102 ms 13916 KB Output is correct
9 Correct 170 ms 8016 KB Output is correct
10 Correct 472 ms 20304 KB Output is correct
11 Correct 296 ms 20776 KB Output is correct
12 Correct 288 ms 19156 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 108 ms 13924 KB Output is correct
15 Correct 27 ms 1884 KB Output is correct
16 Correct 474 ms 20284 KB Output is correct
17 Correct 304 ms 19664 KB Output is correct
18 Correct 300 ms 19536 KB Output is correct
19 Correct 716 ms 59204 KB Output is correct
20 Correct 706 ms 59300 KB Output is correct
21 Correct 717 ms 59216 KB Output is correct
22 Correct 755 ms 59296 KB Output is correct
23 Correct 714 ms 59192 KB Output is correct
24 Correct 722 ms 59220 KB Output is correct
25 Correct 735 ms 59200 KB Output is correct
26 Correct 719 ms 59196 KB Output is correct
27 Correct 720 ms 59340 KB Output is correct
28 Correct 748 ms 59200 KB Output is correct
29 Correct 702 ms 59204 KB Output is correct
30 Correct 705 ms 59220 KB Output is correct