Submission #829223

#	Time	Username	Problem	Language	Result	Execution time	Memory
829223		otarius	Catfish Farm (IOI22_fish)	C++17	Compilation error	0 ms	0 KiB

fish

#include "fish.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long

// #define int long long
// #define int unsigned long long

const ll inf = 1e18 + 7;
const ll weirdMod = 998244353;

int n, m, y, w;
struct segtree {
    ll t[400040];
    void init(int v = 1, int tl = 1, int tr = n) {
        t[v] = -inf;
        if (tl == tr)
            return;
        int tm = (tl + tr) / 2;
        init(2 * v, tl, tm);
        init(2 * v + 1, tm + 1, tr);
    }
    
    void update(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            t[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(2 * v, tl, tm, pos, val);
        else update(2 * v + 1, tm + 1, tr, pos, val);
        t[v] = max(t[2 * v], t[2 * v + 1]);
    }
    
    ll get(int v, int tl, int tr, int l, int r) {
        if (l > r)
            return -inf;
        if (tl == l && tr == r)
            return t[v];
        int tm = (tl + tr) / 2;
        return max(get(2 * v, tl, tm, l, min(r, tm)) +
                   get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
    }
} t1, t2;

vector<pll> pos[100005];
vector<vector<ll>> dp1[100005];
vector<vector<ll>> dp2[100005];
ll max_weights(int N, int M, int[] X, int[] Y, int[] W) {
    n = N; m = M;
    
    for (int i = 0; i < m; i++) {
        X[i]++; Y[i]++;
        pos[X[i]].pb({Y[i], W[i]});
    }
    for (int i = 0; i <= n + 1; i++) {
        sort(pos[i].begin(), pos[i].end());
        if (pos[i].empty() || pos[i][0].ff != 1) pos[i].pb({1, 0});
        if (pos[i].back().ff != n) pos[i].pb({n, 0});
        sort(pos[i].begin(), pos[i].end());
        
        dp1[i] = vector<ll>(pos[i].size(), -inf);
        dp2[i] = vector<ll>(pos[i].size(), -inf);
    }
    
    t1.init(); t2.init();
    
    dp1[0][dp1[0].size() - 1] = 0; dp2[0][0] = 0;
    ll a = -inf, b = -inf, ans = 0;
    for (int i = 0; i <= n + 1; i++) {
        int k = pos[i].size();
        
        if (i >= 1) a = max(a, dp2[i - 1][0]);
        if (i >= 2) b = max(b, dp1[i - 2].back());
        
        dp1[i][0] = max(dp1[i][0], a + pos[i][0].sc);
        if (i >= 2) dp[i][0] = max(dp1[i][0], dp1[i - 2][0] + pos[i][0].sc);
        dp2[i][k - 1] = max(dp2[i][k - 1], b + pos[i][k - 1].sc);
        
        for (int j = 0; j < t; j++) {
            y = pos[i][j].ff;
            w = pos[i][j].sc;
            
            dp1[i][j] = max(dp1[i][j], t1.get(1, 1, n, 1, y - 1) + w);
            t1.update(1, 1, n, y, dp1[i][j]);
        }
        
        for (int j = t - 1; j >= 0; j--) {
            y = pos[i][j].ff;
            w = pos[i][j].sc;
            
            dp2[i][j] = max(dp2[i][j], t2.get(1, 1, n, y + 1, n) + w);
            t2.update(1, 1, n, y, dp2[i][j]);
        }
        
        ans = max(ans, dp2[i][0]);
    }
    
    cout << ans;
}

Compilation message (stderr)

fish.cpp: In member function 'long long int segtree::get(int, int, int, int, int)':
fish.cpp:58:65: error: no matching function for call to 'max(long long int)'
   58 |                    get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
      |                                                                 ^
In file included from /usr/include/c++/10/vector:60,
                 from fish.h:1,
                 from fish.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:
fish.cpp:58:65: note:   candidate expects 2 arguments, 1 provided
   58 |                    get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
      |                                                                 ^
In file included from /usr/include/c++/10/vector:60,
                 from fish.h:1,
                 from fish.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:
fish.cpp:58:65: note:   candidate expects 3 arguments, 1 provided
   58 |                    get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
      |                                                                 ^
In file included from /usr/include/c++/10/algorithm:62,
                 from fish.cpp:3:
/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:
fish.cpp:58:65: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   58 |                    get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
      |                                                                 ^
In file included from /usr/include/c++/10/algorithm:62,
                 from fish.cpp:3:
/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:
fish.cpp:58:65: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   58 |                    get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
      |                                                                 ^
fish.cpp: At global scope:
fish.cpp:65:36: error: expected ',' or '...' before 'X'
   65 | ll max_weights(int N, int M, int[] X, int[] Y, int[] W) {
      |                                    ^
fish.cpp: In function 'long long int max_weights(int, int, int*)':
fish.cpp:69:9: error: 'X' was not declared in this scope
   69 |         X[i]++; Y[i]++;
      |         ^
fish.cpp:69:17: error: 'Y' was not declared in this scope
   69 |         X[i]++; Y[i]++;
      |                 ^
fish.cpp:70:29: error: 'W' was not declared in this scope
   70 |         pos[X[i]].pb({Y[i], W[i]});
      |                             ^
fish.cpp:78:48: error: no match for 'operator=' (operand types are 'std::vector<std::vector<long long int> >' and 'std::vector<long long int>')
   78 |         dp1[i] = vector<ll>(pos[i].size(), -inf);
      |                                                ^
In file included from /usr/include/c++/10/vector:72,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'std::vector<long long int>' to 'const std::vector<std::vector<long long int> >&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from 'std::vector<long long int>' to 'std::vector<std::vector<long long int> >&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from 'std::vector<long long int>' to 'std::initializer_list<std::vector<long long int> >'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
fish.cpp:79:48: error: no match for 'operator=' (operand types are 'std::vector<std::vector<long long int> >' and 'std::vector<long long int>')
   79 |         dp2[i] = vector<ll>(pos[i].size(), -inf);
      |                                                ^
In file included from /usr/include/c++/10/vector:72,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'std::vector<long long int>' to 'const std::vector<std::vector<long long int> >&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from 'std::vector<long long int>' to 'std::vector<std::vector<long long int> >&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from 'std::vector<long long int>' to 'std::initializer_list<std::vector<long long int> >'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
fish.cpp:84:33: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} and 'int')
   84 |     dp1[0][dp1[0].size() - 1] = 0; dp2[0][0] = 0;
      |                                 ^
In file included from /usr/include/c++/10/vector:72,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'int' to 'const std::vector<long long int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from 'int' to 'std::vector<long long int>&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from 'int' to 'std::initializer_list<long long int>'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
fish.cpp:84:48: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'} and 'int')
   84 |     dp1[0][dp1[0].size() - 1] = 0; dp2[0][0] = 0;
      |                                                ^
In file included from /usr/include/c++/10/vector:72,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'int' to 'const std::vector<long long int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from fish.h:1,
                 from fish.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from 'int' to 'std::vector<long long int>&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from 'int' to 'std::initializer_list<long long int>'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
fish.cpp:89:45: error: no matching function for call to 'max(long long int&, __gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type&)'
   89 |         if (i >= 1) a = max(a, dp2[i - 1][0]);
      |                                             ^
In file included from /usr/include/c++/10/vector:60,
                 from fish.h:1,
                 from fish.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:
fish.cpp:89:45: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'})
   89 |         if (i >= 1) a = max(a, dp2[i - 1][0]);
      |                                             ^
In file included from /usr/include/c++/10/vector:60,
                 from fish.h:1,
                 from fish.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:
fish.cpp:89:45: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'})
   89 |         if (i >= 1) a = max(a, dp2[i - 1][0]);
      |                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from fish.cpp:3:
/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:
fish.cpp:89:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   89 |         if (i >= 1) a = max(a, dp2[i - 1][0]);
      |                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from fish.cpp:3:
/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:
fish.cpp:89:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   89 |         if (i >= 1) a = max(a, dp2[i - 1][0]);
      |                                             ^
fish.cpp:90:49: error: no matching function for call to 'max(long long int&, __gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type&)'
   90 |         if (i >= 2) b = max(b, dp1[i - 2].back());
      |                                                 ^
In file included from /usr/include/c++/10/vector:60,
                 from fish.h:1,
                 from fish.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:
fish.cpp:90:49: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'})
   90 |         if (i >= 2) b = max(b, dp1[i - 2].back());
      |                                                 ^
In file included from /usr/include/c++/10/vector:60,
                 from fish.h:1,
                 from fish.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:
fish.cpp:90:49: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<std::vector<long long int> >, std::vector<long long int> >::value_type' {aka 'std::vector<long long int>'})
   90 |         if (i >= 2) b = max(b, dp1[i - 2].back());
      |                                                 ^
In file included from /usr/include/c++/10/algorithm:62,
                 from fish.cpp:3:
/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/substit