Submission #804914

#TimeUsernameProblemLanguageResultExecution timeMemory
804914flappybirdCultivation (JOI17_cultivation)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include <cassert> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define MAX 660 #define MAXS 20 #define INF 20000000000020 #define bb ' ' #define ln '\n' #define Ln '\n' #define MOD 1000000007 ll H, W; int N; pll arr[MAX]; ll ans = INF; int st[MAX * 2], en[MAX * 2]; int U[MAX], D[MAX], UD[MAX]; int A[MAX][MAX], B[MAX][MAX], C[MAX][MAX]; typedef pair<ll, int> pli; pii up[MAX * 2], down[MAX * 2], su[MAX * 2]; ll ys[MAX * 2]; bool test(ll d) { if (d <= 0) return false; int i, j; int p1, p2; p1 = p2 = 1; int X = 0; while (p1 <= N || p2 <= N) { ll x; if (p1 > N) x = arr[p2].second + d; else if (p2 > N) x = arr[p1].second; else x = min(arr[p1].second, arr[p2].second + d); st[X] = en[X] = 0; U[X] = D[X] = UD[X] = 0; ys[X++] = x; while (p1 <= N && arr[p1].second == x) p1++, st[X - 1]++; while (p2 <= N && arr[p2].second + d == x) p2++, en[X - 1]++; } int il, ir; il = ir = 0; for (i = 0; i < X; i++) { ir += st[i]; il += en[i]; if (il == ir) { UD[i] = INF; continue; } U[i] = A[il + 1][ir]; D[i] = B[il + 1][ir]; UD[i] = C[il + 1][ir]; } int ul, dl, udl; int ur, dr, udr; ul = dl = udl = 0; ur = dr = udr = 0; int mn = H * 2 + 10; j = 0; for (i = 0; i < X - 1; i++) { while (ul != ur && up[ur].first <= U[i]) ur--; up[++ur] = pli(U[i], i); while (dl != dr && down[dr].first <= D[i]) dr--; down[++dr] = pli(D[i], i); while (udl != udr && su[udr].first <= UD[i]) udr--; su[++udr] = pli(UD[i], i); while (j + 1 <= i && ys[i + 1] - ys[j + 1] >= W) j++; while (ul != ur && up[ul + 1].second < j) ul++; while (dl != dr && down[dl + 1].second < j) dl++; while (udl != udr && su[udl + 1].second < j) udl++; if (ys[i + 1] - ys[j] >= W) mn = min(mn, max(up[ul + 1].first + down[dl + 1].first, su[udl + 1].first)); } if (mn >= H * 2) return false; ans = min(ans, mn + d - 1); return true; } signed main() { ios::sync_with_stdio(false), cin.tie(0); cin >> H >> W >> N; int i, j, k; vector<ll> ls; ls.push_back(W); for (i = 1; i <= N; i++) cin >> arr[i].first >> arr[i].second; for (i = 1; i <= N; i++) { for (j = i + 1; j <= N; j++) ls.push_back(W - abs(arr[j].second - arr[i].second)); for (j = i + 1; j <= N; j++) ls.push_back(abs(arr[j].second - arr[i].second)); for (j = i + 1; j <= N; j++) ls.push_back(abs(arr[j].second - arr[i].second) + W); ls.push_back(arr[i].second); ls.push_back(W - arr[i].second + 1); } sort(arr + 1, arr + N + 1, [&](pii p1, pii p2) {return p1.second < p2.second; }); for (i = 1; i <= N; i++) { vector<ll> v; A[i][i] = arr[i].first - 1; B[i][i] = H - arr[i].first; v.push_back(arr[i].first); for (j = i + 1; j <= N; j++) { v.insert(lower_bound(v.begin(), v.end(), arr[j].first), arr[j].first); for (k = 0; k + 1 < v.size(); k++) C[i][j] = max(C[i][j], v[k + 1] - v[k] - 1); A[i][j] = v[0] - 1; B[i][j] = H - v.back(); } } sort(ls.begin(), ls.end()); ls.erase(unique(ls.begin(), ls.end()), ls.end()); reverse(ls.begin(), ls.end()); for (auto v : ls) if (!test(v)) break; cout << ans << ln; }

Compilation message (stderr)

cultivation.cpp: In function 'bool test(ll)':
cultivation.cpp:13:13: warning: overflow in conversion from 'long int' to 'int' changes value from '20000000000020' to '-1662697452' [-Woverflow]
   13 | #define INF 20000000000020
      |             ^~~~~~~~~~~~~~
cultivation.cpp:51:12: note: in expansion of macro 'INF'
   51 |    UD[i] = INF;
      |            ^~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for (k = 0; k + 1 < v.size(); k++) C[i][j] = max(C[i][j], v[k + 1] - v[k] - 1);
      |                ~~~~~~^~~~~~~~~~
cultivation.cpp:103:81: error: no matching function for call to 'max(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)'
  103 |    for (k = 0; k + 1 < v.size(); k++) C[i][j] = max(C[i][j], v[k + 1] - v[k] - 1);
      |                                                                                 ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from cultivation.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
cultivation.cpp:103:81: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  103 |    for (k = 0; k + 1 < v.size(); k++) C[i][j] = max(C[i][j], v[k + 1] - v[k] - 1);
      |                                                                                 ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from cultivation.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
cultivation.cpp:103:81: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  103 |    for (k = 0; k + 1 < v.size(); k++) C[i][j] = max(C[i][j], v[k + 1] - v[k] - 1);
      |                                                                                 ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from cultivation.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
cultivation.cpp:103:81: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  103 |    for (k = 0; k + 1 < v.size(); k++) C[i][j] = max(C[i][j], v[k + 1] - v[k] - 1);
      |                                                                                 ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from cultivation.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
cultivation.cpp:103:81: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  103 |    for (k = 0; k + 1 < v.size(); k++) C[i][j] = max(C[i][j], v[k + 1] - v[k] - 1);
      |                                                                                 ^