oj.uz

Submission #861052

# Submission time Handle Problem Language Result Execution time Memory
861052 2023-10-15T08:06:03 Z MongHwa Wall (IOI14_wall) C++17
0 / 100
 167 ms 13924 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
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 Runtime error 2 ms 600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 108 ms 13924 KB Output is correct
3 Runtime error 167 ms 12048 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Runtime error 2 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
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 Runtime error 2 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -