Submission #139767

#TimeUsernameProblemLanguageResultExecution timeMemory
139767BTheroAliens (IOI16_aliens)C++17
Compilation error
0 ms0 KiB
// Why am I so dumb? :c // chrono::system_clock::now().time_since_epoch().count() //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include "aliens.h" #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define debug(x) cerr << #x << " = " << x << '\n'; #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int MAXN = (int)5e4 + 5; const int INF = (int)1e9; const ll LINF = (ll)1e15; struct Line { ll k, b; Line() { k = b = 0ll; } Line(ll k, ll b) : k(k), b(b) {} ll get(ll x) { return k * x + b; } }; double inter(Line a, Line b) { return (double)(a.b - b.b) / (double)(b.k - a.k); } struct CHT { Line H[MAXN]; int sz; CHT() { sz = 0; } bool good(Line a, Line b, Line c) { return inter(a, b) < inter(b, c); } void addLine(Line l) { while (sz >= 2 && !good(H[sz - 2], H[sz - 1], l)) { --sz; } H[sz++] = l; } ll query(ll x) { ll ret = LINF; for (int i = 0; i < sz; ++i) { ret = min(ret, H[i].get(x)); } return ret; } }; pii arr[MAXN]; int n, m, k; bool cmp(pii a, pii b) { if (a.fi == b.fi) { return a.se > b.se; } return a.fi < b.fi; } void resolveOverlaps() { sort(arr + 1, arr + n + 1, cmp); int lim = 0, nn = 0; for (int i = 1; i <= n; ++i) { if (arr[i].se > lim) { arr[++nn] = arr[i]; lim = arr[i].se; } } n = nn; } ll f(int a, int b) { int len = max(0, b - a); return len * 1ll * len; } ll solve() { for (int i = 1; i <= n; ++i) { if (arr[i].fi > arr[i].se) { swap(arr[i].fi, arr[i].se); } ++arr[i].se; } resolveOverlaps(); vector<vector<ll> > dp(k + 5, vector<ll>(n + 5, 0)); for (int i = 0; i <= k; ++i) { fill(dp[i] + 1, dp[i] + n + 1, LINF); } CHT T; for (int lvl = 1; lvl <= k; ++lvl) { T.sz = 0; for (int i = 1; i <= n; ++i) { Line l(-2 * arr[i].fi, dp[lvl - 1][i - 1]); l.b += arr[i].fi * 1ll * arr[i].fi; l.b -= f(arr[i].fi, arr[i - 1].se); T.addLine(l); dp[lvl][i] = T.query(arr[i].se) + arr[i].se * 1ll * arr[i].se; } } return dp[k][n]; } ll take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c) { n = _n; m = _m; k = _k; for (int i = 1; i <= n; ++i) { arr[i] = mp(r[i - 1] + 1, c[i - 1] + 1); } return solve(); }

Compilation message (stderr)

aliens.cpp: In function 'll solve()':
aliens.cpp:125:20: error: no match for 'operator+' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' and 'int')
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/stl_iterator.h:397:5: note: candidate: template<class _Iterator> constexpr std::reverse_iterator<_Iterator> std::operator+(typename std::reverse_iterator<_Iterator>::difference_type, const std::reverse_iterator<_Iterator>&)
     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:397:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/specfun.h:45,
                 from /usr/include/c++/7/cmath:1914,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:41,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/stl_iterator.h:1198:5: note: candidate: template<class _Iterator> constexpr std::move_iterator<_IteratorL> std::operator+(typename std::move_iterator<_IteratorL>::difference_type, const std::move_iterator<_IteratorL>&)
     operator+(typename move_iterator<_Iterator>::difference_type __n,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:1198:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5876:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5876:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:53:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.tcc:1157:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
     operator+(const _CharT* __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.tcc:1157:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   mismatched types 'const _CharT*' and 'std::vector<long long int>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:53:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.tcc:1173:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(_CharT, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.tcc:1173:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>' and 'int'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5913:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5913:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5929:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, _CharT)
     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5929:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5941:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5941:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5947:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&)
     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5947:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5953:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&)
     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5953:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5965:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(const _CharT*, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&)
     operator+(const _CharT* __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5965:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   mismatched types 'const _CharT*' and 'std::vector<long long int>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5971:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(_CharT, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&)
     operator+(_CharT __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5971:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>' and 'int'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5977:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&, const _CharT*)
     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5977:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/bits/basic_string.h:5983:5: note: candidate: template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Alloc> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&, _CharT)
     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/basic_string.h:5983:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/ccomplex:39:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/complex:326:5: note: candidate: template<class _Tp> std::complex<_Tp> std::operator+(const std::complex<_Tp>&, const std::complex<_Tp>&)
     operator+(const complex<_Tp>& __x, const complex<_Tp>& __y)
     ^~~~~~~~
/usr/include/c++/7/complex:326:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'const std::complex<_Tp>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/ccomplex:39:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/complex:335:5: note: candidate: template<class _Tp> std::complex<_Tp> std::operator+(const std::complex<_Tp>&, const _Tp&)
     operator+(const complex<_Tp>& __x, const _Tp& __y)
     ^~~~~~~~
/usr/include/c++/7/complex:335:5: note:   template argument deduction/substitution failed:
aliens.cpp:125:22: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> > >::value_type {aka std::vector<long long int>}' is not derived from 'const std::complex<_Tp>'
         fill(dp[i] + 1, dp[i] + n + 1, LINF);
                      ^
In file included from /usr/include/c++/7/ccomplex:39:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from aliens.cpp:7:
/usr/include/c++/7/complex:344:5: note: candidate: template<class _Tp> std::complex<_Tp> std::operator+(const _Tp&, const std::complex<_Tp>&)
     operator+(const _Tp& __x, const complex<_Tp>& __y)
     ^~~~~~~~
/u