Submission #1131957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131957		anngela	Wall (IOI14_wall)	C++20	0 / 100	0 ms	576 KiB

wall

#include <vector>
#include <algorithm>
using namespace std;

#define fs (x << 1)
#define fd ((x << 1) | 1)
const int MAX_N = 2e6 + 7;
const int INF = 1e9 + 7;

int rez[MAX_N];
int U[4 * MAX_N];
int D[4 * MAX_N];
int t[4 * MAX_N];
int n;

void Dec(int x, int h)
{
	t[x] = min(t[x], h);
	U[x] = min(U[x], h);
	D[x] = min(D[x], h);
}

void Add(int x, int h)
{
	t[x] = max(t[x], h);
	U[x] = max(U[x], h);
	D[x] = max(D[x], h);
}

void PushDown(int x)
{
	if (U[x] != -INF)
	{
		Add(fs, U[x]);
		Add(fd, U[x]);
	}
	if (D[x] != INF)
	{
		Dec(fs, D[x]);
		Dec(fd, D[x]);
	}
	U[x] = -INF; D[x] = INF;
}

void Update(int x, int l, int r, int a, int b, int h, int type)
{
	if (l > b || r < a || l > r)
		return;
	
	if (a <= l && r <= b)
	{
		if (type == 1)
			Add(x, h);
		else 
			Dec(x, h);
		return;
	}
	
	if (l != r) 
		PushDown(x);
	int m = (l + r) / 2;
	Update(fs, l, m, a, b, h, type);
	Update(fd, m + 1, r, a, b, h, type);
}

void Update(int a, int b, int h, int type)
{
	Update(1, 0, n - 1, a, b, h, type);
}

void GetRez(int x, int l, int r)
{
	if (l == r)
	{
		rez[l] = t[x];
		return;
	}
	
	if (l != r) 
		PushDown(x);
	int m = (l + r) / 2;
	GetRez(fs, l, m);
	GetRez(fd, m + 1, r);
}

void GetRez() { GetRez(1, 0, n - 1); }

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  
    for (int i = 0; i < k; ++i)
        Update(left[i], right[i], height[i], op[i]);
    
    GetRez();
    for (int i = 0; i < n; ++i)
		finalHeight[i] = rez[i];
}

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