Submission #834434

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
834434	2023-08-22T14:16:53 Z	Liudas	Progression (NOI20_progression)	C++17	Compilation error	0 ms	0 KB

Progression

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
class segment_tree{
public:
    struct node{
        int l, r;
        int lmax, rmax, midmax;
    };
    vector<node> tree;
    int N;
    segment_tree(int X){
        N = 1;
        while(N <= X){
            N *= 2;
        }
        tree.assign(N * 2, {INT_MIN,INT_MIN,0,0,0});
    }
    node deal_with(node a, node b){
        node c = {INT_MIN,INT_MIN,0,0,0};
        c.l = a.l;
        c.r = b.r;
        c.lmax = a.lmax;
        c.rmax = b.rmax;
        if(a.l == b.l){
            c.lmax += b.lmax;
        }
        if(a.r == b.r){
            c.rmax += a.rmax;
        }
        if(a.r==b.l){
            c.midmax = max(c.midmax, a.rmax + b.lmax);
        }
        c.midmax = max({c.midmax, c.lmax, c.rmax, a.midmax, b.midmax});
        //cout << "A " << a.lmax << " " << a.midmax << " " << a.rmax << endl;
        //cout << "B " << b.lmax << " " << b.midmax << " " << b.rmax << endl;
        //cout << "C " << c.lmax << " " << c.midmax << " " << c.rmax << endl;
        return c;
    }
    void add(int head, int L, int R, int id, int val){
        if(R-L == 1){
            tree[head] = {val, val, 1, 1, 1};
            return;
        }
        int mid = (L + R) / 2;
        if(id < mid){
            add(head * 2 + 1, L, mid, id, val);
        }
        else{
            add(head * 2 + 2, mid, R, id, val);
        }
        tree[head] = deal_with(tree[head*2+1], tree[head*2+2]);
    }
    void add(int id, int val){
        add(0, 0, N, id, val);
    }
    node get(int head, int L, int R, int l, int r){
        if(R - L < 1){
            return {INT_MIN, INT_MIN, 0, 0, 0};
        }
        if(l <= L && R <= r){
            return tree[head];
        }
        if(r <= L || R <= l){
            return {INT_MIN, INT_MIN, 0, 0, 0};
        }
        int mid = (L+R)/2;
        return deal_with(get(head * 2 + 1, L, mid, l, r), get(head * 2 + 2, mid, R, l, r));

    }
    node get(int l, int r){
        return get(0, 0, N, l, r);
    }

};
int main(){
    int N, Q;
    cin >> N >> Q;
    vector<int> arr(N);
    segment_tree tree(N);
    for(int i = 0; i < N; i ++){
        cin >> arr[i];
        if(i > 0){
            tree.add(i, arr[i]-arr[i-1]);
        }
    }
    while(Q--){
        int a;
        cin >> a;
        if(a != 3){
            return 0;
        }
        if(a == 3){
            int b, c;
            cin >> b >> c;
            cout << tree.get(b, c).midmax + 1 <<endl;
        }
    }
    return 0;
}

Compilation message

Progression.cpp: In constructor 'segment_tree::segment_tree(int)':
Progression.cpp:19:29: error: 'INT_MIN' was not declared in this scope
   19 |         tree.assign(N * 2, {INT_MIN,INT_MIN,0,0,0});
      |                             ^~~~~~~
Progression.cpp:5:1: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
    4 | #include <algorithm>
  +++ |+#include <climits>
    5 | using namespace std;
Progression.cpp:19:51: error: no matching function for call to 'std::vector<segment_tree::node>::assign(int, <brace-enclosed initializer list>)'
   19 |         tree.assign(N * 2, {INT_MIN,INT_MIN,0,0,0});
      |                                                   ^
In file included from /usr/include/c++/10/vector:67,
                 from Progression.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:749:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = segment_tree::node; _Alloc = std::allocator<segment_tree::node>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = segment_tree::node]'
  749 |       assign(size_type __n, const value_type& __val)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:749:47: note:   no known conversion for argument 2 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const segment_tree::node&'}
  749 |       assign(size_type __n, const value_type& __val)
      |                             ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note: candidate: 'template<class _InputIterator, class> void std::vector<_Tp, _Alloc>::assign(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = segment_tree::node; _Alloc = std::allocator<segment_tree::node>]'
  768 |  assign(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from Progression.cpp:1:
/usr/include/c++/10/bits/stl_iterator_base_types.h: In substitution of 'template<class _InIter> using _RequireInputIter = std::__enable_if_t<std::is_convertible<typename std::iterator_traits< <template-parameter-1-1> >::iterator_category, std::input_iterator_tag>::value> [with _InIter = int]':
/usr/include/c++/10/bits/stl_vector.h:766:9:   required from here
/usr/include/c++/10/bits/stl_iterator_base_types.h:249:11: error: no type named 'iterator_category' in 'struct std::iterator_traits<int>'
  249 |     using _RequireInputIter =
      |           ^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/vector:67,
                 from Progression.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:794:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::initializer_list<_Tp>) [with _Tp = segment_tree::node; _Alloc = std::allocator<segment_tree::node>]'
  794 |       assign(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:794:7: note:   candidate expects 1 argument, 2 provided
Progression.cpp: In member function 'segment_tree::node segment_tree::deal_with(segment_tree::node, segment_tree::node)':
Progression.cpp:22:19: error: 'INT_MIN' was not declared in this scope
   22 |         node c = {INT_MIN,INT_MIN,0,0,0};
      |                   ^~~~~~~
Progression.cpp:22:19: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
Progression.cpp: In member function 'segment_tree::node segment_tree::get(int, int, int, int, int)':
Progression.cpp:61:21: error: 'INT_MIN' was not declared in this scope
   61 |             return {INT_MIN, INT_MIN, 0, 0, 0};
      |                     ^~~~~~~
Progression.cpp:61:21: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
Progression.cpp:61:46: error: could not convert '{<expression error>, INT_MIN, 0, 0, 0}' from '<brace-enclosed initializer list>' to 'segment_tree::node'
   61 |             return {INT_MIN, INT_MIN, 0, 0, 0};
      |                                              ^
      |                                              |
      |                                              <brace-enclosed initializer list>
Progression.cpp:67:21: error: 'INT_MIN' was not declared in this scope
   67 |             return {INT_MIN, INT_MIN, 0, 0, 0};
      |                     ^~~~~~~
Progression.cpp:67:21: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
Progression.cpp:67:46: error: could not convert '{<expression error>, INT_MIN, 0, 0, 0}' from '<brace-enclosed initializer list>' to 'segment_tree::node'
   67 |             return {INT_MIN, INT_MIN, 0, 0, 0};
      |                                              ^
      |                                              |
      |                                              <brace-enclosed initializer list>