#include<bits/stdc++.h>
using namespace std;
int N, R, C, x[309], y[309];
const int INF = 1e9 + 100;
long long ans = 1LL << 60;
set < int > sa, sb, sab;
namespace ds {
multiset < int > xs, dx;
void init ()
{
xs.clear (), dx.clear ();
}
void delDif (int x)
{
dx.erase (dx.find (x));
}
void add (int x)
{
if (xs.find (x) != xs.end ()) xs.insert (x);
else
{
xs.insert (x);
auto it1 = xs.lower_bound (x), it2 = xs.upper_bound (x);
if (it1 != xs.begin () && it2 != xs.end ())
it1 --,
delDif ((*it2) - (*it1)),
it1 ++;
if (it1 != xs.begin ())
it1 --,
dx.insert (x - (*it1));
if (it2 != xs.end ())
dx.insert ((*it2) - x);
}
}
void del (int x)
{
if (xs.count (x) >= 2) xs.erase (xs.find (x));
else
{
auto it1 = xs.lower_bound (x), it2 = xs.upper_bound (x);
if (it1 != xs.begin () && it2 != xs.end ())
it1 --,
dx.insert ((*it2) - (*it1)),
it1 ++;
if (it1 != xs.begin ())
it1 --,
delDif (x - (*it1));
if (it2 != xs.end ())
delDif ((*it2) - x);
xs.erase (x);
}
}
int maxDif ()
{
if (dx.empty ()) return 0;
return *(dx.rbegin ());
}
int getA ()
{
if (xs.empty ()) return INF;
return (*xs.begin ()) - 1;
}
int getB ()
{
if (xs.empty ()) return INF;
return C - (*xs.rbegin ());
}
}
long long pos[1209];
int nr, stat[1209][3];
vector < pair < long long, int > > events;
deque < int > dq[3];
void clearDeque ()
{
for (int i=0; i<3; i++)
while (!dq[i].empty ())
dq[i].pop_back ();
}
void add (int pos)
{
for (int i=0; i<3; i++)
{
while (!dq[i].empty () && stat[dq[i].back ()][i] <= stat[pos][i])
dq[i].pop_back ();
dq[i].push_back (pos);
}
}
void del (int pos)
{
for (int i=0; i<3; i++)
while (!dq[i].empty () && dq[i].front () <= pos)
dq[i].pop_front ();
}
int getSum ()
{
if (dq[0].empty ()) return 2 * INF;
int minA = stat[dq[0].front ()][0], minB = stat[dq[1].front ()][1], minAB = stat[dq[2].front ()][2];
return max (minA + minB, minAB);
}
void solve (int updown)
{
ds::init ();
events.clear ();
clearDeque ();
for (int i=1; i<=N; i++)
{
events.push_back ({x[i], -y[i]});
events.push_back ({x[i] + updown + 1, y[i]});
}
sort (events.begin (), events.end ()), nr = 0;
for (int ii=0; ii<events.size (); ii++)
{
int jj = ii;
while (jj < events.size () && events[jj].first == events[ii].first)
{
if (events[jj].second < 0) ds::add (-events[jj].second);
else ds::del (events[jj].second);
jj ++;
}
jj --;
///[ii, jj]
nr ++, pos[nr] = events[ii].first;
stat[nr][0] = ds::getA ();
stat[nr][1] = ds::getB ();
stat[nr][2] = ds::maxDif () - 1;
///
ii = jj;
}
///we want [i, j] so that pos[j + 1] - pos[i - 1] - 1 >= updown
///and max (max (stat[k][0]) + max (stat[k][1]), max (stat[k][2])) is minimal for i<=k<=j
pos[nr + 1] = pos[nr] - 1, pos[0] = pos[1] - 1;
int i = 1;
/*printf ("%d ->\n", updown);
for (int i=1; i<=nr; i++)
printf ("%7lld %7d %7d %7d\n", pos[i], stat[i][0], stat[i][1], stat[i][2]);*/
for (int j=1; j<=nr; j++)
{
add (j);
while (pos[j + 1] - pos[i] - 1 >= R)
del (i), i ++;
if (pos[j + 1] - pos[i - 1] - 1 >= R)
{
long long curr = updown + getSum ();
if (curr < ans)
ans = curr;
}
}
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d %d\n", &R, &C);
scanf ("%d", &N);
for (int i=1; i<=N; i++)
scanf ("%d %d", &x[i], &y[i]);
for (int i=1; i<=N; i++)
sa.insert (x[i] - 1), sb.insert (R - x[i]);
for (int i=1; i<=N; i++)
for (int j=i + 1; j<=N; j++)
if (x[i] != x[j])
{
int val = x[i] - x[j];
if (val < 0) val = -val;
sab.insert (val - 1);
}
for (auto a : sa)
for (auto b : sb)
sab.insert (a + b);
for (auto ab : sab)
solve (ab);
printf ("%lld\n", ans);
return 0;
}
Compilation message
cultivation.cpp: In function 'void solve(int)':
cultivation.cpp:127:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int ii=0; ii<events.size (); ii++)
~~^~~~~~~~~~~~~~~
cultivation.cpp:130:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (jj < events.size () && events[jj].first == events[ii].first)
~~~^~~~~~~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:171:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d\n", &R, &C);
~~~~~~^~~~~~~~~~~~~~~~~~~
cultivation.cpp:172:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &N);
~~~~~~^~~~~~~~~~
cultivation.cpp:174:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &x[i], &y[i]);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
488 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
632 KB |
Output is correct |
| 8 |
Correct |
2 ms |
632 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
632 KB |
Output is correct |
| 11 |
Correct |
2 ms |
632 KB |
Output is correct |
| 12 |
Correct |
2 ms |
632 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
488 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
632 KB |
Output is correct |
| 8 |
Correct |
2 ms |
632 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
632 KB |
Output is correct |
| 11 |
Correct |
2 ms |
632 KB |
Output is correct |
| 12 |
Correct |
2 ms |
632 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
488 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
632 KB |
Output is correct |
| 8 |
Correct |
2 ms |
632 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
632 KB |
Output is correct |
| 11 |
Correct |
2 ms |
632 KB |
Output is correct |
| 12 |
Correct |
2 ms |
632 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
488 KB |
Output is correct |
| 4 |
Correct |
2 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
632 KB |
Output is correct |
| 8 |
Correct |
2 ms |
632 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
2 ms |
632 KB |
Output is correct |
| 11 |
Correct |
2 ms |
632 KB |
Output is correct |
| 12 |
Correct |
2 ms |
632 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
