oj.uz

Submission #794847

# Submission time Handle Problem Language Result Execution time Memory
794847 2023-07-27T01:06:55 Z maeola Pyramid Base (IOI08_pyramid_base) C++17
90 / 100
 5000 ms 55828 KB 
// 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31632 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31532 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 31652 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31692 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 31696 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 31696 KB Output is correct
2 Correct 116 ms 31700 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 31700 KB Output is correct
2 Correct 102 ms 31700 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31956 KB Output is correct
2 Correct 60 ms 32064 KB Output is correct
3 Correct 63 ms 31956 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 32692 KB Output is correct
2 Correct 208 ms 32732 KB Output is correct
3 Correct 170 ms 32720 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 32960 KB Output is correct
2 Correct 109 ms 32864 KB Output is correct
3 Correct 57 ms 32840 KB Output is correct
4 Correct 385 ms 33116 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 33352 KB Output is correct
2 Correct 455 ms 33352 KB Output is correct
3 Correct 130 ms 33420 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 33568 KB Output is correct
2 Correct 607 ms 33656 KB Output is correct
3 Correct 561 ms 33652 KB Output is correct
4 Correct 601 ms 33656 KB Output is correct
5 Correct 541 ms 33644 KB Output is correct
6 Correct 112 ms 33736 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2583 ms 43864 KB Output is correct
2 Correct 700 ms 43296 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3762 ms 49900 KB Output is correct
2 Correct 3066 ms 49492 KB Output is correct
3 Correct 333 ms 49052 KB Output is correct

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5030 ms 55828 KB Time limit exceeded
2 Halted 0 ms 0 KB -