제출 #47096

#제출 시각아이디문제언어결과실행 시간메모리
47096SpaimaCarpatilorCultivation (JOI17_cultivation)C++17
80 / 100
2076 ms2428 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; 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]; 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 i = 1; for (int j=1; j<=nr && pos[j] <= updown + R; j++) { unsigned int rightEnd = min ((unsigned int) updown + R, pos[j + 1] - 1); add (j); if (rightEnd >= R) { while (pos[i + 1] - 1 < rightEnd - R + 1) 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 cntsab, sab[309 * 309 * 3 / 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]) sab[++cntsab] = x[j] - x[i] - 1; int minVal = 0; for (int i=1; i<N; i++) if (x[i + 1] - x[i] - 1 > minVal) minVal = x[i + 1] - x[i] - 1; for (auto a : sa) for (auto b : sb) sab[++cntsab] = a + b; sort (sab + 1, sab + cntsab + 1); for (int i=1; i<=cntsab; i++) if ((i == 1 || sab[i] != sab[i - 1]) && ans > sab[i] && sab[i] >= minVal) solve (sab[i]); printf ("%d\n", ans); return 0; }

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

cultivation.cpp: In function 'void solve(int)':
cultivation.cpp:135:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (r < N && x[r + 1] <= t)
                         ~~~~~~~~~^~~~
cultivation.cpp:137:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (x[l] + updown < t && l <= N)
                ~~~~~~~~~~~~~~^~~
cultivation.cpp:146:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=1; j<=nr && pos[j] <= updown + R; j++)
                            ~~~~~~~^~~~~~~~~~~~~
cultivation.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (rightEnd >= R)
             ~~~~~~~~~^~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:208:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ((i == 1 || sab[i] != sab[i - 1]) && ans > sab[i] && sab[i] >= minVal)
                                             ~~~~^~~~~~~~
cultivation.cpp: In function 'void readAndSort()':
cultivation.cpp:164: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:165:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &N);
     ~~~~~~^~~~~~~~~~
cultivation.cpp:167: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...