Submission #404024

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
404024	2021-05-13T17:03:37 Z	ScarletS	Index (COCI21_index)	C++17	Compilation error	0 ms	0 KB

index

#include <bits/stdc++.h>
using namespace std;

struct pst {
    struct node {
        int val;
        node *l, *r;
        node(ll x) : val(x) {}
    };
    deque<node> buffer;
    node *newnode(int x = 0) {
        buffer.emplace_back(x);
        return &buffer.back();
    }
    node *merge(node *l, node *r) {
        auto x = newnode(l->val + r->val);
        x->l = l, x->r = r;
        return x;
    }
    int n, a=0;
    node *roots[200005];
    pst(int n) : n(n) {roots[0] = build(1, n);}
    node *build(int l, int r) {
        if(l == r) 
            return newnode();
        return merge(build(l,(l+r)>>1),build((l+r+2)>>1, r));
    }
    node *update(node *v, int l, int r, int i, int x) {
        if(r < i || i < l)
            return v;
        if(l == r)
            return newnode(v->val+x);
        return merge(update(v->l,l,(l+r)>>1,i,x), update(v->r,(l+r+2)>>1,r,i,x));
    }
    void update(int k, int i, int x) {
        roots[k] = update(roots[k], 1, n, i, x);
    }
    ll query(node *v, int cL, int cR, int l, int r) {
        if (r<cL||cR<l)
            return 0;
        if (l<=cL&&cR<=r)
            return v->val;
        return query(v->l,cL,(cL+cR)>>1,l,r) + query(v->r,(cL+cR+2)>>1,cR,l,r);
    }
    ll query(int k, int l, int r) {
        return query(roots[k],1,n,l,r);
    }
    void clone(int k) {
        roots[++a] = merge(roots[k]->l, roots[k]->r);
        roots[a]->val = roots[k]->val;
    }
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,q,x,L,R,l,r,m;
    cin>>n>>q;
    pst seg(n);
    for (int i=1;i<=n;++i)
    {
        cin>>x;
        seg.clone(i-1);
        seg.update(i,x,1);
    }
    while (q--)
    {
        cin>>L>>R;
        l=1;r=n;
        while (l<r)
        {
            m=l+(r-l)/2+1;
            x = seg.query(R,m,n) - seg.query(L-1,m,n);
            if (x<m)
                r=m-1;
            else
                l=m;
        }
        cout<<l<<"\n";
    }
    return 0;
}

Compilation message

index.cpp:8:16: error: expected ')' before 'x'
    8 |         node(ll x) : val(x) {}
      |             ~  ^~
      |                )
index.cpp:38:5: error: 'll' does not name a type
   38 |     ll query(node *v, int cL, int cR, int l, int r) {
      |     ^~
index.cpp:45:5: error: 'll' does not name a type
   45 |     ll query(int k, int l, int r) {
      |     ^~
index.cpp: In function 'int main()':
index.cpp:73:21: error: 'struct pst' has no member named 'query'
   73 |             x = seg.query(R,m,n) - seg.query(L-1,m,n);
      |                     ^~~~~
index.cpp:73:40: error: 'struct pst' has no member named 'query'
   73 |             x = seg.query(R,m,n) - seg.query(L-1,m,n);
      |                                        ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 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 index.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = pst::node; _Args = {int&}; _Tp = pst::node]':
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = pst::node; _Args = {int&}; _Tp = pst::node; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<pst::node>]'
/usr/include/c++/10/bits/deque.tcc:170:30:   required from 'std::deque<_Tp, _Alloc>::reference std::deque<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int&}; _Tp = pst::node; _Alloc = std::allocator<pst::node>; std::deque<_Tp, _Alloc>::reference = pst::node&]'
index.cpp:12:30:   required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'pst::node::node(int&)'
  150 |  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
index.cpp:5:12: note: candidate: 'pst::node::node()'
    5 |     struct node {
      |            ^~~~
index.cpp:5:12: note:   candidate expects 0 arguments, 1 provided
index.cpp:5:12: note: candidate: 'constexpr pst::node::node(const pst::node&)'
index.cpp:5:12: note:   no known conversion for argument 1 from 'int' to 'const pst::node&'
index.cpp:5:12: note: candidate: 'constexpr pst::node::node(pst::node&&)'
index.cpp:5:12: note:   no known conversion for argument 1 from 'int' to 'pst::node&&'