#include<bits/stdc++.h>
using namespace std;
int budget, N, M, K;
const int maxX = 1000000;
int mi[4 * maxX + 100], b[4 * maxX + 100], l[4 * maxX + 100], r[4 * maxX + 100], lzy[4 * maxX + 100];
void split (int &nod, int &f1, int &f2)
{
if (lzy[nod] == 0) return ;
lzy[f1] += lzy[nod], mi[f1] += lzy[nod];
lzy[f2] += lzy[nod], mi[f2] += lzy[nod];
lzy[nod] = 0;
}
void refresh (int &nod, int &f1, int &f2, int &mij, int &st, int &dr)
{
if (mi[f1] == mi[f2])
b[nod] = max ({b[f1], b[f2], r[f1] + l[f2]}),
l[nod] = (l[f1] == mij - st + 1 ? l[f1] + l[f2] : l[f1]),
r[nod] = (r[f2] == dr - mij ? r[f2] + r[f1] : r[f2]);
else
if (mi[f1] < mi[f2])
b[nod] = b[f1],
l[nod] = l[f1], r[nod] = 0;
else
b[nod] = b[f2],
r[nod] = r[f2], r[nod] = 0;
}
void build (int nod, int st, int dr)
{
mi[nod] = 0, l[nod] = r[nod] = b[nod] = dr - st + 1;
if (st == dr) return ;
int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
build (f1, st, mij);
build (f2, mij + 1, dr);
}
void update (int nod, int st, int dr, int x, int y, int xtra)
{
if (x <= st && dr <= y)
{
mi[nod] += xtra, lzy[nod] += xtra;
return ;
}
int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
split (nod, f1, f2);
if (x <= mij) update (f1, st, mij, x, y, xtra);
if (mij < y) update (f2, mij + 1, dr, x, y, xtra);
refresh (nod, f1, f2, mij, st, dr);
}
int query ()
{
if (mi[1] != 0) return 0;
return b[1];
}
void add (int y1, int y2, int sg)
{
update (1, 1, M, y1, y2, sg);
}
vector < pair < pair < int, int >, int > > v[maxX + 100];
void addLine (int line, int sg)
{
for (auto it : v[line])
if (sg * it.second > 0) add (it.first.first, it.first.second, it.second);
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d %d", &N, &M);
scanf ("%d", &budget);
scanf ("%d", &K), build (1, 1, M);
for (int i=1; i<=K; i++)
{
int x1, y1, x2, y2, c;
scanf ("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
if (budget == 0) c = (c > 0);
v[x1].push_back ({{y1, y2}, +c});
v[x2].push_back ({{y1, y2}, -c});
}
int L = 0, x2 = 0;
for (int x1=1; x1<=N - L + 1; x1++)
{
while (x2 < x1 + L)
x2 ++, addLine (x2, +1);
while (query () > L)
{
L ++;
//printf ("%d %d %d\n", x1, x2, query ());
if (x2 < N)
x2 ++, addLine (x2, +1);
else
break;
}
addLine (x1, -1);
}
printf ("%d\n", L);
return 0;
}
Compilation message
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:78:7: 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:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &budget);
~~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:80:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &K), build (1, 1, M);
~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
pyramid_base.cpp:84:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
23800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23920 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
23972 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
24780 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
29268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
61960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
61960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
61960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
61960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
67012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
67308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
68768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1041 ms |
84408 KB |
Output is correct |
| 2 |
Incorrect |
422 ms |
84408 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1511 ms |
101796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1691 ms |
109984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
