제출 #531484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531484		tkwiatkowski	벽 (IOI14_wall)	C++17	32 / 100	3074 ms	18956 KiB

wall

/*
	Zadanie: Wall
	Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

struct segTree {
	vector<pair<int, int>> t_min;
	vector<pair<int, int>> lazy;
	vector<pair<int, int>> t_max;
	int BASE;

	segTree(int n)
	{
		BASE = 1;
		while (BASE <= n)
			BASE *= 2;
		t_min.resize(2*BASE + 7, {1e9, 0});
		t_max.resize(2*BASE + 7, {0, 0});
		lazy.resize(2*BASE + 7, {-1, 0});
		for (int i = 0; i < BASE; ++i)
			t_min[BASE + i] = t_max[BASE + i] = {0, i};
		for (int i = BASE - 1; i > 0; --i) {
			t_min[i] = min(t_min[2*i], t_min[2*i + 1]);
			t_max[i] = max(t_max[2*i], t_max[2*i + 1]);
		}
	}

	void Update(int v)
	{
		if (lazy[v].fi == -1)
			return;
		t_min[2*v] = t_max[2*v] = lazy[v];
		t_min[2*v + 1] = t_max[2*v + 1] = lazy[v];
		lazy[2*v] = lazy[2*v + 1] = lazy[v];
		lazy[v] = {-1, 0};
	}

	void Set(int a, int b, pair<int, int> val, int v = 1, int l = 0, int r = -1)
	{
		if (r == -1)
			r = BASE - 1;
		if (b < l || r < a)
			return;
		if (a <= l && r <= b) {
			t_min[v] = t_max[v] = val;
			lazy[v] = val;
			return;
		}
		int mid = (l + r)/2;
		Update(v);
		Set(a, b, val, 2*v, l, mid);
		Set(a, b, val, 2*v + 1, mid + 1, r);
		t_min[v] = min(t_min[2*v], t_min[2*v + 1]);
		t_max[v] = max(t_max[2*v], t_max[2*v + 1]);
	}

	pair<int, int> Min(int a, int b, int v = 1, int l = 0, int r = -1)
	{
		if (r == -1)
			r = BASE - 1;
		if (b < l || r < a)
			return {1e9, 0};
		if (a <= l && r <= b)
			return t_min[v];
		int mid = (l + r)/2;
		Update(v);
		auto res_l = Min(a, b, 2*v, l, mid);
		auto res_r = Min(a, b, 2*v + 1, mid + 1, r);
		t_min[v] = min(t_min[2*v], t_min[2*v + 1]);
		t_max[v] = max(t_max[2*v], t_max[2*v + 1]);
		return min(res_l, res_r);
	}

	pair<int, int> Max(int a, int b, int v = 1, int l = 0, int r = -1)
	{
		if (r == -1)
			r = BASE - 1;
		if (b < l || r < a)
			return {0, 0};
		if (a <= l && r <= b)
			return t_max[v];
		int mid = (l + r)/2;
		Update(v);
		auto res_l = Max(a, b, 2*v, l, mid);
		auto res_r = Max(a, b, 2*v + 1, mid + 1, r);
		t_min[v] = min(t_min[2*v], t_min[2*v + 1]);
		t_max[v] = max(t_max[2*v], t_max[2*v + 1]);
		return max(res_l, res_r);
	}
};

struct segTree2 {
	vector<pair<int, int>> t;
	int BASE;
	int c;

	segTree2(int n)
	{
		c = 0;
		BASE = 1;
		while (BASE <= n)
			BASE *= 2;
		t.resize(2*BASE + 7, {0, 0});
	}

	void Set(int a, int b, int val)
	{
		++c;
		a += BASE - 1;
		b += BASE + 1;
		while (a/2 != b/2) {
			if (a % 2 == 0)
				t[a + 1] = {c, val};
			if (b % 2 == 1)
				t[b - 1] = {c, val};
			a /= 2;
			b /= 2;
		}
	}

	int Get(int i)
	{
		i += BASE;
		pair<int, int> res = t[i];
		while (i /= 2)
			res = max(res, t[i]);
		return res.se;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	segTree h(n);
	segTree2 lt(n), rt(n);
	lt.Set(0, n - 1, 0);
	rt.Set(0, n - 1, n - 1);
	for (int i = 0; i < k; ++i) {
		if (op[i] == 1) {
			auto res = h.Min(left[i], right[i]);
			while (res.fi < height[i]) {
				int l = lt.Get(res.se);
				int r = rt.Get(res.se);
				if (l < left[i]) {
					rt.Set(l, left[i] - 1, left[i] - 1);
					l = left[i];
				}
				if (r > right[i]) {
					lt.Set(right[i] + 1, r, right[i] + 1);
					h.Set(right[i] + 1, r, {res.fi, right[i] + 1});
					r = right[i];
				}
				h.Set(l, r, {height[i], l});
				if (h.Max(l - 1, l - 1).fi == height[i])
					l = lt.Get(l - 1);
				if (h.Max(r + 1, r + 1).fi == height[i])
					r = rt.Get(r + 1);
				lt.Set(l, r, l);
				rt.Set(l, r, r);
				res = h.Min(left[i], right[i]);
			}
		} else {
			auto res = h.Max(left[i], right[i]);
			while (res.fi > height[i]) {
				int l = lt.Get(res.se);
				int r = rt.Get(res.se);
				if (l < left[i]) {
					rt.Set(l, left[i] - 1, left[i] - 1);
					l = left[i];
				}
				if (r > right[i]) {
					lt.Set(right[i] + 1, r, right[i] + 1);
					h.Set(right[i] + 1, r, {res.fi, right[i] + 1});
					r = right[i];
				}
				h.Set(l, r, {height[i], l});
				if (h.Max(l - 1, l - 1).fi == height[i])
					l = lt.Get(l - 1);
				if (h.Max(r + 1, r + 1).fi == height[i])
					r = rt.Get(r + 1);
				lt.Set(l, r, l);
				rt.Set(l, r, r);
				res = h.Max(left[i], right[i]);
			}
		}
	}
	for (int i = 1; i < h.BASE; ++i)
		h.Update(i);
	for (int i = 0; i < n; ++i)
		finalHeight[i] = h.t_max[h.BASE + i].fi;
	return;
}

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