#include<bits/stdc++.h>
using namespace std;
int budget, N, M, K;
namespace solver0 {
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], l[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)
{
//printf ("[%d %d] %d\n", y1, y2, 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);
}
void readAndSolve ()
{
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);
v[x1].push_back ({{y1, y2}, +1});
v[x2].push_back ({{y1, y2}, -1});
}
int L = 0, x2 = 0;
for (int x1=1; x1<=N - L; 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);
}
};
namespace solverNon0 {
const int maxX = 30000;
int P, mi[4 * maxX + 100], lzy[4 * maxX + 100];
vector < int > normX, normY;
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 build (int nod, int st, int dr)
{
mi[nod] = lzy[nod] = 0;
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);
mi[nod] = min (mi[f1], mi[f2]);
}
void add (int L, int y1, int y2, int sg)
{
///[y, y+L-1] intersects [y1, y2]
///y >= max (1, y1 - L + 1), y <= min (y2, M - L + 1)
int l = max (1, y1 - L + 1), r = min (y2, M - L + 1);
l = lower_bound (normY.begin (), normY.end (), l) - normY.begin () + 1;
r = upper_bound (normY.begin (), normY.end (), r) - normY.begin ();
if (l <= r)
update (1, 1, P, l, r, sg);
}
vector < pair < pair < int, int >, int > > v[1000100];
void addLine (int L, int line, int sg)
{
for (auto it : v[line])
if (sg * it.second > 0)
add (L, it.first.first, it.first.second, it.second);
}
bool ok (int L)
{
P = upper_bound (normY.begin (), normY.end (), M - L + 1) - normY.begin ();
build (1, 1, P);
int j = 0;
for (int i=0; i + 1<normX.size (); i++)
{
addLine (L, normX[i], +1);
int x2 = normX[i + 1] - 1;
while (x2 - normX[j] + 1 > L)
addLine (L, normX[j], -1), j ++;
if (mi[1] <= budget && x2 >= L)
return 1;
}
return 0;
}
void readAndSolve ()
{
scanf ("%d", &K);
for (int i=1; i<=K; i++)
{
int x1, y1, x2, y2, c;
scanf ("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
normX.push_back (x1), normX.push_back (x2);
normY.push_back (y1 + 1);
v[x1].push_back ({{y1, y2}, +c});
v[x2].push_back ({{y1, y2}, -c});
}
sort (normX.begin (), normX.end ());
normX.erase (unique (normX.begin (), normX.end ()), normX.end ());
normY.push_back (1), sort (normY.begin (), normY.end ());
normY.erase (unique (normY.begin (), normY.end ()), normY.end ());
P = normY.size (), normX.push_back (N + 1);
int p = 1, u = min (N, M), mij, ras = 0;
while (p <= u)
{
mij = (p + u) >> 1;
if (ok (mij)) ras = mij, p = mij + 1;
else u = mij - 1;
}
printf ("%d\n", ras);
}
};
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d %d", &N, &M);
scanf ("%d", &budget);
if (budget == 0)
{
solver0::readAndSolve ();
return 0;
}
solverNon0::readAndSolve ();
return 0;
}
Compilation message
pyramid_base.cpp: In function 'bool solverNon0::ok(int)':
pyramid_base.cpp:165:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i + 1<normX.size (); i++)
~~~~~^~~~~~~~~~~~~~
pyramid_base.cpp: In function 'void solver0::readAndSolve()':
pyramid_base.cpp:78:25: 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:82:19: 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);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In function 'void solverNon0::readAndSolve()':
pyramid_base.cpp:179:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &K);
~~~~~~^~~~~~~~~~
pyramid_base.cpp:183:19: 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);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:210: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:211:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &budget);
~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
47352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
47364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
47548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
48356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
52896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
85536 KB |
Output is correct |
| 2 |
Correct |
116 ms |
86276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
86276 KB |
Output is correct |
| 2 |
Correct |
87 ms |
86276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
86276 KB |
Output is correct |
| 2 |
Correct |
115 ms |
86276 KB |
Output is correct |
| 3 |
Correct |
92 ms |
86276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
86276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
276 ms |
86276 KB |
Output is correct |
| 2 |
Correct |
74 ms |
86276 KB |
Output is correct |
| 3 |
Incorrect |
147 ms |
86276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
475 ms |
86276 KB |
Output is correct |
| 2 |
Incorrect |
792 ms |
86276 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
387 ms |
86276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
922 ms |
102556 KB |
Output is correct |
| 2 |
Correct |
390 ms |
102556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1258 ms |
106064 KB |
Output is correct |
| 2 |
Correct |
1259 ms |
108336 KB |
Output is correct |
| 3 |
Correct |
634 ms |
108336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1541 ms |
108336 KB |
Output is correct |
| 2 |
Correct |
2005 ms |
113076 KB |
Output is correct |
| 3 |
Correct |
2169 ms |
113100 KB |
Output is correct |
| 4 |
Correct |
1830 ms |
113100 KB |
Output is correct |
| 5 |
Correct |
1056 ms |
113100 KB |
Output is correct |
