Submission #47076

#TimeUsernameProblemLanguageResultExecution timeMemory
47076SpaimaCarpatilorCultivation (JOI17_cultivation)C++17
0 / 100
5 ms704 KiB
#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] = 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; for (int i=1; i<=nr; i++) { if (pos[i] - 1 <= updown) relevantShifts.push_back (pos[i] - 1); if (pos[i] - R >= 0 && pos[i] - R <= updown) relevantShifts.push_back (pos[i] - R); } relevantShifts.push_back (updown); sort (relevantShifts.begin (), relevantShifts.end ()); 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 = 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 (stderr)

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:177: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:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
 ~~~~~~^~~~~~~~~~
cultivation.cpp:180: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]);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...