#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;
struct ban
{
int x1, y1, x2, y2, b;
};
int n, m, b;
int q;
ban a[N];
vector<int> va[N], vh[N];
int t[N * 4];
int laz[N * 4];
void shi(int pos)
{
if (laz[pos] == 0)
return;
t[pos * 2] += laz[pos];
t[pos * 2 + 1] += laz[pos];
laz[pos * 2] += laz[pos];
laz[pos * 2 + 1] += laz[pos];
laz[pos] = 0;
}
void bil(int tl, int tr, int pos)
{
t[pos] = 0;
laz[pos] = 0;
if (tl == tr)
{
return;
}
int m = (tl + tr) / 2;
bil(tl, m, pos * 2);
bil(m + 1, tr, pos * 2 + 1);
}
void ubd(int tl, int tr, int l, int r, int y, int pos)
{
if (l > r)
return;
if (tl == l && tr == r)
{
t[pos] += y;
laz[pos] += y;
return;
}
shi(pos);
int m = (tl + tr) / 2;
ubd(tl, m, l, min(m, r), y, pos * 2);
ubd(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
t[pos] = min(t[pos * 2], t[pos * 2 + 1]);
}
bool stg(int u)
{
bil(1, m - u + 1, 1);
for (int i = 1; i <= u; ++i)
{
for (int j = 0; j < va[i].size(); ++j)
{
int k = va[i][j];
ubd(1, m - u + 1, max(a[k].y1 - u + 1, 1), min(a[k].y2, m - u + 1), a[k].b, 1);
}
}
if (t[1] <= b)
return true;
for (int i = 2; i <= n - u + 1; ++i)
{
for (int j = 0; j < va[i + u - 1].size(); ++j)
{
int k = va[i + u - 1][j];
ubd(1, m - u + 1, max(a[k].y1 - u + 1, 1), min(a[k].y2, m - u + 1), a[k].b, 1);
}
for (int j = 0; j < vh[i - 1].size(); ++j)
{
int k = vh[i - 1][j];
ubd(1, m - u + 1, max(a[k].y1 - u + 1, 1), min(a[k].y2, m - u + 1), -a[k].b, 1);
}
if (t[1] <= b)
return true;
}
return false;
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
#endif // SOMETHING
scanf("%d%d", &n, &m);
scanf("%d", &b);
scanf("%d", &q);
for (int i = 1; i <= q; ++i)
scanf("%d%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2, &a[i].b);
for (int i = 1; i <= q; ++i)
{
va[a[i].x1].push_back(i);
vh[a[i].x2].push_back(i);
}
int l = 1, r = min(n, m);
int ans = 0;
while (l <= r)
{
int m = (l + r) / 2;
if (stg(m))
{
ans = m;
l = m + 1;
}
else
r = m - 1;
}
printf("%d\n", ans);
return 0;
}
Compilation message
pyramid_base.cpp: In function 'bool stg(int)':
pyramid_base.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < va[i].size(); ++j)
~~^~~~~~~~~~~~~~
pyramid_base.cpp:74:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < va[i + u - 1].size(); ++j)
~~^~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vh[i - 1].size(); ++j)
~~^~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
pyramid_base.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b);
~~~~~^~~~~~~~~~
pyramid_base.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
pyramid_base.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2, &a[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
42 ms |
47352 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
46 ms |
47232 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
49 ms |
47304 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
50 ms |
47608 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
73 ms |
49412 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
142 ms |
55672 KB |
Output is correct |
| 2 |
Correct |
405 ms |
63864 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
323 ms |
63868 KB |
Output is correct |
| 2 |
Correct |
177 ms |
55544 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
56 ms |
47872 KB |
Output is correct |
| 2 |
Correct |
97 ms |
47992 KB |
Output is correct |
| 3 |
Correct |
87 ms |
47952 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
221 ms |
51036 KB |
Output is correct |
| 2 |
Correct |
383 ms |
51012 KB |
Output is correct |
| 3 |
Correct |
362 ms |
50936 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
485 ms |
57712 KB |
Output is correct |
| 2 |
Correct |
95 ms |
49604 KB |
Output is correct |
| 3 |
Correct |
263 ms |
64884 KB |
Output is correct |
| 4 |
Correct |
641 ms |
66040 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
642 ms |
66540 KB |
Output is correct |
| 2 |
Correct |
1171 ms |
66296 KB |
Output is correct |
| 3 |
Correct |
264 ms |
58488 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
478 ms |
58952 KB |
Output is correct |
| 2 |
Correct |
1457 ms |
66928 KB |
Output is correct |
| 3 |
Correct |
1383 ms |
66908 KB |
Output is correct |
| 4 |
Correct |
1538 ms |
66812 KB |
Output is correct |
| 5 |
Correct |
1509 ms |
67036 KB |
Output is correct |
| 6 |
Correct |
214 ms |
59000 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5094 ms |
84728 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5050 ms |
94484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5060 ms |
103992 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
