Submission #794847

#	Time	Username	Problem	Language	Result	Execution time	Memory
794847		maeola	Pyramid Base (IOI08_pyramid_base)	C++17	90 / 100	5030 ms	55828 KiB

pyramid_base

// trans rights
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ALL(x) begin(x), end(x)
 
int M, N, B, P;
 
vector<tuple<int, int, int, int>> add, rm;
 
struct Node
{
	uint sum, mn;
};
 
Node nodes[4000005];
 
void upd(int i, int l, int r, int ql, int qr, int x)
{
	auto &node = nodes[i];
	if (ql <= l and qr >= r)
	{
		node.sum += x;
	}
	else
	{
		int m = (l + r) / 2;
		if (ql <= m)
			upd(2 * i, l, m, ql, qr, x);
		if (qr > m)
			upd(2 * i + 1, m + 1, r, ql, qr, x);
	}
	node.mn = l == r
		      ? node.sum
		      : (node.sum + min(nodes[2 * i].mn, nodes[2 * i + 1].mn));
}
 
bool ok(int sz)
{
	int b = M - sz + 1;
	memset(nodes, 0, sizeof(nodes));
	int p1 = 0, p2 = 0;
	for (int i = 1; i <= N; i++)
	{
		while (p1 < P and get<0>(add[p1]) <= i)
		{
			auto [y, x1, x2, c] = add[p1++];
			upd(1, 1, b, x1 - sz + 1, x2, c);
		}
		if (i >= sz)
		{
			while (p2 < P and get<0>(rm[p2]) <= i - sz + 1)
			{
				auto [y, x1, x2, c] = rm[p2++];
				upd(1, 1, b, x1 - sz + 1, x2, -c);
			}
			if (nodes[1].mn <= (uint)B)
				return true;
		}
	}
	return false;
}
 
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> M >> N >> B >> P;
	for (int i = 0; i < P; i++)
	{
		int x1, y1, x2, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		c = c > B ? B + 1 : c;
		add.push_back({y1, x1, x2, c});
		rm.push_back({y2 + 1, x1, x2, c});
	}
	sort(ALL(add));
	sort(ALL(rm));
	int a = 0, b = min(N, M) + 1;
	while (b - a > 1)
	{
		int m = (a + b) / 2;
		if (ok(m))
			a = m;
		else
			b = m;
	}
	cout << a;
	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: 10 / 10
• Subtask 15: 0 / 10