제출 #47095

#제출 시각아이디문제언어결과실행 시간메모리
47095SpaimaCarpatilorCultivation (JOI17_cultivation)C++17
80 / 100
2057 ms8184 KiB
#include<bits/stdc++.h> using namespace std; int N, R, C, x[309], y[309], precalc[309][309][3]; const int INF = 1e9 + 100; unsigned int ans = UINT_MAX; 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; } }; unsigned int pos[1209]; int nr, stat[1209][3]; int dq[3][1209], fst[3], lst[3]; void clearDeque () { for (int i=0; i<3; i++) fst[i] = 1, lst[i] = 0; } void add (int pos) { for (int i=0; i<3; i++) { while (fst[i] <= lst[i] && stat[dq[i][lst[i]]][i] <= stat[pos][i]) lst[i] --; dq[i][++lst[i]] = pos; } } void del (int pos) { for (int i=0; i<3; i++) while (fst[i] <= lst[i] && dq[i][fst[i]] <= pos) fst[i] ++; } int getSum () { if (fst[0] > lst[0]) return 2 * INF; int minA = stat[dq[0][fst[0]]][0], minB = stat[dq[1][fst[1]]][1], minAB = stat[dq[2][fst[2]]][2]; return max (minA + minB, minAB); } unsigned int relevantXs[609], relevantX1[309], relevantX2[309]; unsigned int relevantShifts[1209], relevantS1[609], relevantS2[609]; void solve (int updown) { ds::init (); clearDeque (); for (int i=1; i<=N; i++) relevantX2[i] = x[i] + updown + 1; merge (relevantX1 + 1, relevantX1 + N + 1, relevantX2 + 1, relevantX2 + N + 1, relevantXs + 1); nr = 1, pos[1] = -0, stat[1][0] = INF, stat[1][1] = INF, stat[1][2] = -1; int l = 1, r = 0; for (int currPos = 1; currPos <= 2 * N; currPos ++) { unsigned int t = relevantXs[currPos]; 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] = UINT_MAX; int n = 0, m = 0, p = 0; for (int i=1; i<=nr; i++) { if (i > 1 && pos[i] - 1 <= updown) relevantS1[++n] = pos[i] - 1; if (pos[i] >= R && pos[i] - R <= updown) relevantS2[++m] = pos[i] - R; } merge (relevantS1 + 1, relevantS1 + n + 1, relevantS2 + 1, relevantS2 + m + 1, relevantShifts + 1); p = n + m, relevantShifts[++p] = updown; int j = 1, i = 1; for (int currPos = 1; currPos <= p; currPos ++) if (currPos == 1 || relevantShifts[currPos] != relevantShifts[currPos - 1]) { unsigned int shift = relevantShifts[currPos]; while (j <= nr && pos[j] <= R + shift) add (j), j++; while (pos[i + 1] - 1 < 1 + shift) del (i), i ++; unsigned int curr = 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]), relevantX1[i] = 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) { if (ans >= ab) solve (ab); } printf ("%d\n", ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

cultivation.cpp: In function 'void solve(int)':
cultivation.cpp:136:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (r < N && x[r + 1] <= t)
                         ~~~~~~~~~^~~~
cultivation.cpp:138:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (x[l] + updown < t && l <= N)
                ~~~~~~~~~~~~~~^~~
cultivation.cpp:149:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i > 1 && pos[i] - 1 <= updown)
                      ~~~~~~~~~~~^~~~~~~~~
cultivation.cpp:151:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pos[i] >= R && pos[i] - R <= updown)
             ~~~~~~~^~~~
cultivation.cpp:151:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pos[i] >= R && pos[i] - R <= updown)
                            ~~~~~~~~~~~^~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:217:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ans >= ab)
         ~~~~^~~~~
cultivation.cpp: In function 'void readAndSort()':
cultivation.cpp:174: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:175:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~
cultivation.cpp:177: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 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...