Submission #879631

#	Time	Username	Problem	Language	Result	Execution time	Memory
879631		aykhn	Wall (IOI14_wall)	C++17	100 / 100	789 ms	67156 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

int N;
int ans[2000000];

struct SegTree
{
	int sz;
	vector<pair<int, int>> st;
	void init(int n)
	{
		sz = 1;
		while (sz < n) sz <<= 1;
		st.assign(sz << 1, {-1, 0});
	}
	void build(int l, int r, int x)
	{
		if (l + 1 == r)
		{
			st[x] = {0, 0};
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, 2*x + 1);
		build(mid, r, 2*x + 2);
		return;
	}
	void relax(int l, int r, int x)
	{
		if (l + 1 == r) return;
		int l1 = st[x].first;
		int r1 = st[x].second;
		int l2 = st[2*x + 1].first;
		int r2 = st[2*x + 1].second;
		if (l1 >= r2) st[2*x + 1] = {l1, l1};
		else if (r1 <= l2) st[2*x + 1] = {r1, r1};
		else st[2*x + 1] = {max(l1, l2), min(r1, r2)};
		l2 = st[2*x + 2].first, r2 = st[2*x + 2].second;
		if (l1 >= r2) st[2*x + 2] = {l1, l1};
		else if (r1 <= l2) st[2*x + 2] = {r1, r1};
		else st[2*x + 2] = {max(l1, l2), min(r1, r2)};
		st[x] = {0, 1e5};
	}
	void make(int l, int r, int x, int lx, int rx, int t, int val)
	{
		relax(l, r, x);
		if (l >= rx || r <= lx) return;
		if (l >= lx && r <= rx)
		{
			if (l + 1 == r)
			{
				if (t == 1) st[x] = {max(val, st[x].first), max(val, st[x].first)};
				else st[x] = {min(val, st[x].first), min(val, st[x].first)};
				return;
			}
			if (t == 1) st[x] = {val, 1e5};
			else st[x] = {0, val};
			relax(l, r, x);
			return;
		}
		int mid = (l + r) >> 1;
		make(l, mid, 2*x + 1, lx, rx, t, val);
		make(mid, r, 2*x + 2, lx, rx, t, val);
		return;
	}
	void final(int l, int r, int x)
	{
		if (l + 1 == r) 
		{
			if (l < N) ans[l] = st[x].first;
			return;
		}
		relax(l, r, x);
		int mid = (l + r) >> 1;
		final(l, mid, 2*x + 1);
		final(mid, r, 2*x + 2);
		return;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	SegTree st;
	N = n;
	st.init(n);
	for (int q = 0; q < k; q++)
	{
		int t = op[q];
		int lx = left[q];
		int rx = right[q];
		int val = height[q];
		st.make(0, st.sz, 0, lx, rx + 1, t, val);
	}
	st.final(0, st.sz, 0);
	for (int i = 0; i < n; i++)
	{
		finalHeight[i] = max(0, ans[i]);
	}
}

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