Submission #1144585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144585		arashmemar	Pyramid Base (IOI08_pyramid_base)	C++20	80 / 100	5097 ms	177332 KiB

pyramid_base

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5e4;
int inf = 2e9;
int n, m;

vector <pair <int, pair <int, int>>> add[2 * maxn], rem[2 * maxn];
pair <pair <pair <int, int>, pair <int, int>>, int> ps[maxn];
long long int v[2 * maxn], lazy[2 * maxn];

void spread(int id)
{
	v[id] += lazy[id];
	if (id < maxn)
	{
		lazy[id * 2 + 0] += lazy[id];
		lazy[id * 2 + 1] += lazy[id];
	}
	lazy[id] = 0;
	return ;
}

void updatep(int id, int L, int R, int l, int r, long long int val)
{
	if (L == l and R == r)
	{
		lazy[id] += val;
		spread(id);
		return ;
	}
	spread(id);
	int mid = (L + R) / 2;
	if (l < mid)
	{
		updatep(id * 2 + 0, L, mid, l, min(mid, r), val);
	}
	if (r > mid)
	{
		updatep(id * 2 + 1, mid, R, max(l, mid), r, val);
	}
	if (l >= mid)
	{
		spread(id * 2 + 0);
	}
	if (r <= mid)
	{
		spread(id * 2 + 1);
	}
	v[id] = min(v[id * 2 + 0], v[id * 2 + 1]);
	return ;
}

long long int getp()
{
	return v[1];
}

pair <int, int> update(int id, int L, int R, int l, int r)
{
	if (L == l and R == r)
	{
		return {id, id};
	}
	int mid = (L + R) / 2;
	pair <int, int> ret, tmp;
	ret = tmp = {0, 0};
	if (l < mid)
	{
		ret = update(id * 2 + 0, L, mid, l, min(r, mid));
	}
	if (r > mid)
	{
		tmp = update(id * 2 + 1, mid, R, max(l, mid), r);
		ret.second = tmp.second;
		if (ret.first == 0)
		{
			ret.first = tmp.first;
		}
	}
	return ret;
}

void inc(int id)
{
	for (auto o : add[id])
	{
		updatep(1, 1, n + 1, o.second.first, o.second.second, o.first);
	}
	return ;
}

void del(int id)
{
	for (auto o : rem[id])
	{
		updatep(1, 1, n + 1, o.second.first, o.second.second, -o.first);
	}
	return ;
}

long long int get(int id, int L, int R)
{
	inc(id);
	if (R - L == 1)
	{
		long long int ret = getp();
		del(id);
		return ret;
	}
	int mid = (L + R) / 2;
	long long int tmp1 = get(id * 2 + 0, L, mid);
	long long int tmp2 = get(id * 2 + 1, mid, R);

	long long int ret = min(tmp1, tmp2);
	del(id);
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int b, p;
	cin >> m >> n >> b >> p;

	unsigned int a = 0;

	int l = 0, r = min(n, m) + 1;

	for (int i = 0;i < p;i++)
	{
		int x1, y1, x2, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		ps[i] = {{{y1, y2}, {x1, x2}}, c};
	}

	if (b == 0)
	{
		while (r - l > 1)
		{
			int mid = (l + r) / 2;
			for (int i = 0;i < min(p, 200000);i++)
			{
				auto o = ps[i];
				int y1 = o.first.first.first, y2 = o.first.first.second, x1 = o.first.second.first, x2 = o.first.second.second, c = o.second;
				add[max(1, x1 - mid + 1)].push_back({c, {max(1, y1 - mid + 1), min(n + 1 - mid + 1, y2 + 1)}});
				rem[x2].push_back({c, {max(1, y1 - mid + 1), min(n + 1 - mid + 1, y2 + 1)}});
			}

			bool nok = 1;

			for (int i = 1;i <= m - mid + 1;i++)
			{
				for (auto o : add[i])
				{
					updatep(1, 1, n + 1 - mid + 1, o.second.first, o.second.second, 1);
				}
				if (getp() == 0)
				{
					nok = 0;
					break;
				}
				for (auto o : rem[i])
				{
					updatep(1, 1, n + 1 - mid + 1, o.second.first, o.second.second, -1);
				}
			}
			if (nok)
			{
				r = mid;
			}
			else
			{
				l = mid;
			}

			for (int i = 0;i < 2 * maxn;i++)
			{
				add[i].clear();
				rem[i].clear();
				lazy[i] = v[i] = 0;
			}
		}
		cout << l;
		return 0;
	}

	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		for (int i = 0;i < p;i++)
		{
			auto o = ps[i];
			int y1 = o.first.first.first, y2 = o.first.first.second, x1 = o.first.second.first, x2 = o.first.second.second, c = o.second;
			pair <int, int> tmp = update(1, 1, m + 1, max(1, x1 - mid + 1), x2 + 1);
			add[tmp.first].push_back({c, {max(1, y1 - mid + 1), y2 + 1}});
			rem[tmp.second].push_back({c, {max(1, y1 - mid + 1), y2 + 1}});
		}

		if (mid > 1)
		{
			int y1 = m - mid + 2, y2 = m, x1 = 1, x2 = n;
			long long int c = inf;
			pair <int, int> tmp = update(1, 1, m + 1, y1, y2 + 1);
			add[tmp.first].push_back({c, {x1, x2 + 1}});
			rem[tmp.second].push_back({c, {x1, x2 + 1}});
			y1 = 1, y2 = m, x1 = n - mid + 2, x2 = n;
			tmp = update(1, 1, m + 1, y1, y2 + 1);
			add[tmp.first].push_back({c, {x1, x2 + 1}});
			rem[tmp.second].push_back({c, {x1, x2 + 1}});
		}

		long long int tmp = get(1, 1, m + 1);

		if (tmp <= b)
		{
			l = mid;
		}
		else
		{
			r = mid;
		}

		for (int i = 0;i < 2 * maxn;i++)
		{
			add[i].clear();
			rem[i].clear();
			v[i] = lazy[i] = 0;
		}
	}
	cout << l;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 10 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10