oj.uz

Submission #794846

# Submission time Handle Problem Language Result Execution time Memory
794846 2023-07-27T01:06:26 Z maeola Pyramid Base (IOI08_pyramid_base) C++17
0 / 100
 3 ms 400 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()
{
#ifndef DEBUG
	freopen("pbs.in", "r", stdin);
	freopen("pbs.out", "w", stdout);
#endif
	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;
}

Compilation message

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:67:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  freopen("pbs.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:68:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  freopen("pbs.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -