#include<bits/stdc++.h>
using namespace std;
int N, R, C, x[309], y[309], precalc[309][309][3];
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 ());
}
void store (int &a, int &b, int &df)
{
a = getA ();
b = getB ();
df = maxDif () - 1;
}
};
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 ();
clearDeque ();
vector < long long > relevantXs, relevantX1, relevantX2;
for (int i=1; i<=N; i++)
relevantX1.push_back (x[i]),
relevantX2.push_back (x[i] + updown + 1);
relevantXs.resize (relevantX1.size () + relevantX2.size ());
merge (relevantX1.begin (), relevantX1.end (), relevantX2.begin (), relevantX2.end (), relevantXs.begin ());
nr = 1, pos[1] = -(1LL << 60), stat[1][0] = INF, stat[1][1] = INF, stat[1][2] = -1;
int l = 1, r = 0;
for (auto t : relevantXs)
{
while (r < N && x[r + 1] <= t)
r ++;
while (x[l] + updown < t && l <= N)
l ++;
nr ++, pos[nr] = t;
stat[nr][0] = precalc[l][r][0];
stat[nr][1] = precalc[l][r][1];
stat[nr][2] = precalc[l][r][2];
}
pos[nr + 1] = 1LL << 60;
/* 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]);*/
vector < long long > relevantShifts, relevantS1, relevantS2;
for (int i=1; i<=nr; i++)
{
if (pos[i] - 1 <= updown) relevantS1.push_back (pos[i] - 1);
if (pos[i] - R >= 0 && pos[i] - R <= updown) relevantS2.push_back (pos[i] - R);
}
relevantShifts.resize (relevantS1.size () + relevantS2.size ());
merge (relevantS1.begin (), relevantS1.end (), relevantS2.begin (), relevantS2.end (), relevantShifts.begin ());
relevantShifts.push_back (updown);
int j = 1, i = 1;
for (auto shift : relevantShifts)
{
while (j <= nr && pos[j] <= R + shift)
add (j), j++;
while (pos[i + 1] - 1 < 1 + shift)
del (i), i ++;
long long curr = (long long) updown + getSum ();
if (curr < ans)
ans = curr;
}
}
void readAndSort ()
{
pair < int, int > point[309];
scanf ("%d %d\n", &R, &C);
scanf ("%d", &N);
for (int i=1; i<=N; i++)
scanf ("%d %d", &point[i].first, &point[i].second);
sort (point + 1, point + N + 1);
for (int i=1; i<=N; i++)
x[i] = point[i].first, y[i] = point[i].second;
}
void doPrecalc ()
{
for (int i=1; i<=N + 1; i++)
{
ds::init ();
ds::store (precalc[i][i - 1][0], precalc[i][i - 1][1], precalc[i][i - 1][2]);
for (int j=i; j<=N; j++)
ds::add (y[j]),
ds::store (precalc[i][j][0], precalc[i][j][1], precalc[i][j][2]);
}
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
readAndSort ();
doPrecalc ();
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 readAndSort()':
cultivation.cpp:176:11: 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:177:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &N);
~~~~~~^~~~~~~~~~
cultivation.cpp:179:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &point[i].first, &point[i].second);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
