Submission #541741

#	Time	Username	Problem	Language	Result	Execution time	Memory
541741		keta_tsimakuridze	Cake 3 (JOI19_cake3)	C++14	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

cake3

#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define f first #define s second #define endl "\n" const int N = 2e5 + 5, mod = 1e9 + 7; //! int t, n, ans = 0, val[N], a[N], f[N]; pii p[N]; struct node{ int cn, sum; } tree[4 * N]; int m; void add(int u, int l, int r, int id, int t) { if(l > id || r < id) return; if(l == r) { tree[u].cn += t; tree[u].sum += t * val[id]; return; } int mid = (l + r) / 2; add(2 * u, l, mid, id, t); add(2 * u + 1, mid + 1, r, id, t); tree[u].cn = tree[2 * u].cn + tree[2 * u + 1].cn; tree[u].sum = tree[2 * u].sum + tree[2 * u + 1].sum; } int add(int id, int t) { add(1, 1, n, id, t); } int get(int u,int l,int r,int k) { if(l == r) { return min(tree[u].cn, k) * val[l]; } int mid = (l + r) / 2; if(tree[2 * u + 1].cn < k) return tree[2 * u + 1].sum + get(2 * u, l, mid, k - tree[2 * u + 1].cn); return get(2 * u + 1, mid + 1, r, k); } void solve(int l,int r,int ql, int qr) { if(r < l) return; int mid = (l + r) >> 1, sum = 0; pii opt; opt = {-2e15, 1}; multiset<int> s; for(int i = mid; i >= max(l, qr + 1); i--) add(a[i], 1), f[i]++; for(int i = min(qr, mid - 1); i >= ql; i--) { add(a[i], 1); f[i]++; if(mid - i + 1 >= m) opt = max({get(1, 1, n, m) - 2 * (p[mid].f - p[i].f), i}, opt); } // cout << mid << " _ " << opt.f << " " << opt.s << endl; ans = max(ans, opt.f); for(int i = mid; i >= max(l, qr + 1); i--) add(a[i], -1), f[i]--; for(int i = min(qr, mid - 1); i >= ql; i--) add(a[i], -1), f[i]--; if(l == r) return; for(int i = opt.s + 1; i <= l - 1; i++) add(a[i], 1), f[i]++; solve(l, mid - 1, ql, opt.s); for(int i = opt.s + 1; i <= l - 1; i++) add(a[i], -1), f[i]--; for(int i = qr + 1; i <= mid; i++) add(a[i], 1), f[i]++; solve(mid + 1,r, opt.s, qr); for(int i = qr + 1; i <= mid; i++) add(a[i], -1), f[i]--; } main() { ios_base::sync_with_stdio(false), cin.tie(0),cout.tie(0); cin >> n >> m; ans = -2e9; vector<pii> x; for(int i = 1; i <= n; i++) { cin >> p[i].s >> p[i].f; } sort(p + 1, p + n + 1); for(int i = 1; i <= n; i++) { x.push_back({p[i].s, i}); } sort(x.begin(), x.end()); int cur = 0; for(int i = 0; i < x.size(); i++) { if(x[i].f != x[i - 1].f) cur++; val[cur] = x[i].f; a[x[i].s] = cur; } solve(m, n, 1, n - m + 1); cout << ans; }

Compilation message (stderr)

cake3.cpp: In function 'long long int add(long long int, long long int)':
cake3.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
   31 | }
      | ^
cake3.cpp: In function 'void solve(long long int, long long int, long long int, long long int)':
cake3.cpp:50:64: error: no match for 'operator=' (operand types are 'std::pair<long long int, long long int>' and 'long long int')
   50 |   opt = max({get(1, 1, n, m) - 2 * (p[mid].f - p[i].f), i}, opt);
      |                                                                ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from cake3.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<long long int, long long int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from 'long long int' to 'std::conditional<true, const std::pair<long long int, long long int>&, const std::__nonesuch&>::type' {aka 'const std::pair<long long int, long long int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<long long int, long long int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from 'long long int' to 'std::conditional<true, std::pair<long long int, long long int>&&, std::__nonesuch&&>::type' {aka 'std::pair<long long int, long long int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
cake3.cpp:50:64: note:   mismatched types 'const std::pair<_T1, _T2>' and 'long long int'
   50 |   opt = max({get(1, 1, n, m) - 2 * (p[mid].f - p[i].f), i}, opt);
      |                                                                ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from cake3.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
cake3.cpp:50:64: note:   mismatched types 'std::pair<_T1, _T2>' and 'long long int'
   50 |   opt = max({get(1, 1, n, m) - 2 * (p[mid].f - p[i].f), i}, opt);
      |                                                                ^
cake3.cpp:42:26: warning: unused variable 'sum' [-Wunused-variable]
   42 |  int mid = (l + r) >> 1, sum = 0;
      |                          ^~~
cake3.cpp: At global scope:
cake3.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main() {
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:80:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from cake3.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = const long long int*; _Iterator2 = const long long int*; _Compare = std::pair<long long int, long long int>]':
/usr/include/c++/10/bits/stl_algo.h:5700:12:   required from 'constexpr _ForwardIterator std::__max_element(_ForwardIterator, _ForwardIterator, _Compare) [with _ForwardIterator = const long long int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<std::pair<long long int, long long int> >]'
/usr/include/c++/10/bits/stl_algo.h:5751:43:   required from 'constexpr _FIter std::max_element(_FIter, _FIter, _Compare) [with _FIter = const long long int*; _Compare = std::pair<long long int, long long int>]'
/usr/include/c++/10/bits/stl_algo.h:3487:31:   required from 'constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare) [with _Tp = long long int; _Compare = std::pair<long long int, long long int>]'
cake3.cpp:50:64:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: no match for call to '(std::pair<long long int, long long int>) (const long long int&, const long long int&)'
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~