Submission #219239

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219239	2020-04-04T16:36:11 Z	2fat2code	Santa Claus (RMI19_santa)	C++17	Compilation error	0 ms	0 KB

santa

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int mod=1e9+7;
const int modp=1999999973;
const int modulo=998244353;

const int nmax=100005;

int t,n,x[nmax],v[nmax],tree[4*nmax],lazy[4*nmax];
bitset<nmax>h;

void build(int l,int r,int nod){
    if(l==r){
        tree[nod]=lazy[nod]=0;
    }
    else{
        int mid=l+(r-l)/2;
        tree[nod]=lazy[nod]=0;
        build(l,mid,2*nod);
        build(mid+1,r,2*nod+1);
    }
    return;
}

void push(int l,int r,int nod){
    if(lazy[nod]!=0){
        tree[nod]+=lazy[nod];
        if(l!=r){
            lazy[2*nod]+=lazy[nod];
            lazy[2*nod+1]+=lazy[nod];
        }
        lazy[nod]=0;
    }
    return;
}

void update(int l,int r,int le,int re,int val,int nod){
    push(le,re,nod);
    if(l>re || r<le) return;
    else if(le>=l && re<=r){
        lazy[nod]+=val;
        push(le,re,nod);
        return;
    }
    else{
        int mid=le+(re-le)/2;
        update(l,r,le,mid,val,2*nod);
        update(l,r,mid+1,re,val,2*nod+1);
        tree[nod]=min(tree[2*nod],tree[2*nod+1]);
        return;
    }
}


int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
  //  ifstream cin("input.in");
  //  ofstream cout("output.out");
    cin >> t;
    while(t--){
        int lastelf=0;
        build(1,nmax,1);
        cin >> n;
        for(int i=1;i<=n;i++) cin >> x[i];
        for(int i=1;i<=n;i++){
            int tz;
            cin >> tz;
            h[i]=tz;
            if(h[i]==0) lastelf=i;
        }
        for(int i=1;i<=n;i++) {
            cin >> v[i];
            ++v[i];
        }
        int left_max=0,curr=1;
        if(h[1]==0) update(v[1],nmax,1,nmax,-1,1);
        if(h[1]==1) update(v[1],nmax,1,nmax,1,1);
        while(curr<=n && (curr<lastelf || tree[1]<0)){
            cout << "-1 ";
            ++curr;
            if(curr<=n){
                if(h[curr]==0) update(v[curr],nmax,1,nmax,-1,1);
                if(h[curr]==1) update(v[curr],nmax,1,nmax,1,1);
            }
        }
        if(curr<=n){
            multiset<int>gifts;
            for(int i=curr;i<=n;i++){
                bool ok=false;
                do{
                    if(left_max>=(i-1)) break;
                    ok=false;
                    if(h[left_max+1]==1){
                        update(v[left_max+1],nmax,1,nmax,-1,1);
                        if(tree[1]>=0){
                            left_max++;
                            ok=true;
                        }
                        else{
                            auto it=gifts.lower_bound(v[left_max+1]);
                            if(it!=gifts.end()){
                                update(*it,nmax,1,nmax,1,1);
                                if(tree[1]>=0){
                                    ok=true;
                                    gifts.erase(gifts.find(it));
                                    left_max++;
                                }
                                else{
                                    update(*it,nmax,1,nmax,-1,1);
                                    update(v[left_max+1],nmax,1,nmax,1,1);
                                }
                            }
                            else update(v[left_max+1],nmax,1,nmax,1,1);
                        }
                    }
                    else{
                        left_max++;
                        gifts.insert(v[left_max]);
                        ok=true;
                    }
                }while(ok==true);
                if(i+1<=n) update(v[i+1],nmax,1,nmax,1,1);
                cout << 2LL*x[i] - x[left_max+1] << ' ';
                }
        }
        cout << '\n';
    }
}

Compilation message

santa.cpp: In function 'int32_t main()':
santa.cpp:121:62: error: no matching function for call to 'std::multiset<long long int>::find(std::_Rb_tree_const_iterator<long long int>&)'
                                     gifts.erase(gifts.find(it));
                                                              ^
In file included from /usr/include/c++/7/set:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:87,
                 from santa.cpp:3:
/usr/include/c++/7/bits/stl_multiset.h:746:7: note: candidate: std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::find(const key_type&) [with _Key = long long int; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<long long int>; std::multiset<_Key, _Compare, _Alloc>::key_type = long long int]
       find(const key_type& __x)
       ^~~~
/usr/include/c++/7/bits/stl_multiset.h:746:7: note:   no known conversion for argument 1 from 'std::_Rb_tree_const_iterator<long long int>' to 'const key_type& {aka const long long int&}'
/usr/include/c++/7/bits/stl_multiset.h:750:7: note: candidate: std::multiset<_Key, _Compare, _Alloc>::const_iterator std::multiset<_Key, _Compare, _Alloc>::find(const key_type&) const [with _Key = long long int; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<long long int>; std::multiset<_Key, _Compare, _Alloc>::key_type = long long int]
       find(const key_type& __x) const
       ^~~~
/usr/include/c++/7/bits/stl_multiset.h:750:7: note:   no known conversion for argument 1 from 'std::_Rb_tree_const_iterator<long long int>' to 'const key_type& {aka const long long int&}'
/usr/include/c++/7/bits/stl_multiset.h:756:2: note: candidate: template<class _Kt> decltype (std::multiset<_Key, _Compare, _Alloc>::iterator{((std::multiset<_Key, _Compare, _Alloc>*)this)->std::multiset<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::multiset<_Key, _Compare, _Alloc>::find(const _Kt&) [with _Kt = _Kt; _Key = long long int; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>]
  find(const _Kt& __x)
  ^~~~
/usr/include/c++/7/bits/stl_multiset.h:756:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_multiset.h: In substitution of 'template<class _Kt> decltype (std::multiset<long long int>::iterator{((std::multiset<long long int>*)this)->std::multiset<long long int>::_M_t.std::_Rb_tree<long long int, long long int, std::_Identity<long long int>, std::less<long long int>, std::allocator<long long int> >::_M_find_tr(__x)}) std::multiset<long long int>::find<_Kt>(const _Kt&) [with _Kt = std::_Rb_tree_const_iterator<long long int>]':
santa.cpp:121:62:   required from here
/usr/include/c++/7/bits/stl_multiset.h:756:2: error: no matching function for call to 'std::_Rb_tree<long long int, long long int, std::_Identity<long long int>, std::less<long long int>, std::allocator<long long int> >::_M_find_tr(const std::_Rb_tree_const_iterator<long long int>&)'
In file included from /usr/include/c++/7/map:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from santa.cpp:3:
/usr/include/c++/7/bits/stl_tree.h:1212:2: note: candidate: template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_find_tr(const _Kt&) [with _Kt = _Kt; _Req = _Req; _Key = long long int; _Val = long long int; _KeyOfValue = std::_Identity<long long int>; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>]
  _M_find_tr(const _Kt& __k)
  ^~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1212:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_tree.h:1209:9: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<long long int>, std::_Rb_tree_const_iterator<long long int>, void>'
         typename _Req =
         ^~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1222:2: note: candidate: template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_find_tr(const _Kt&) const [with _Kt = _Kt; _Req = _Req; _Key = long long int; _Val = long long int; _KeyOfValue = std::_Identity<long long int>; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>]
  _M_find_tr(const _Kt& __k) const
  ^~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1222:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_tree.h:1219:9: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<long long int>, std::_Rb_tree_const_iterator<long long int>, void>'
         typename _Req =
         ^~~~~~~~
In file included from /usr/include/c++/7/set:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:87,
                 from santa.cpp:3:
/usr/include/c++/7/bits/stl_multiset.h:756:2: error: no matching function for call to 'std::_Rb_tree_const_iterator<long long int>::_Rb_tree_const_iterator(<brace-enclosed initializer list>)'
  find(const _Kt& __x)
  ^~~~
In file included from /usr/include/c++/7/map:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from santa.cpp:3:
/usr/include/c++/7/bits/stl_tree.h:348:7: note: candidate: std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator(const iterator&) [with _Tp = long long int; std::_Rb_tree_const_iterator<_Tp>::iterator = std::_Rb_tree_iterator<long long int>]
       _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:348:7: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/7/bits/stl_tree.h:345:7: note: candidate: std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator(std::_Rb_tree_const_iterator<_Tp>::_Base_ptr) [with _Tp = long long int; std::_Rb_tree_const_iterator<_Tp>::_Base_ptr = const std::_Rb_tree_node_base*]
       _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:345:7: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/7/bits/stl_tree.h:341:7: note: candidate: std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator() [with _Tp = long long int]
       _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:341:7: note:   candidate expects 0 arguments, 1 provided
/usr/include/c++/7/bits/stl_tree.h:326:12: note: candidate: constexpr std::_Rb_tree_const_iterator<long long int>::_Rb_tree_const_iterator(const std::_Rb_tree_const_iterator<long long int>&)
     struct _Rb_tree_const_iterator
            ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:326:12: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/7/bits/stl_tree.h:326:12: note: candidate: constexpr std::_Rb_tree_const_iterator<long long int>::_Rb_tree_const_iterator(std::_Rb_tree_const_iterator<long long int>&&)
/usr/include/c++/7/bits/stl_tree.h:326:12: note:   conversion of argument 1 would be ill-formed:
In file included from /usr/include/c++/7/set:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:87,
                 from santa.cpp:3:
/usr/include/c++/7/bits/stl_multiset.h:762:2: note: candidate: template<class _Kt> decltype (std::multiset<_Key, _Compare, _Alloc>::const_iterator{((const std::multiset<_Key, _Compare, _Alloc>*)this)->std::multiset<_Key, _Compare, _Alloc>::_M_t._M_find_tr(__x)}) std::multiset<_Key, _Compare, _Alloc>::find(const _Kt&) const [with _Kt = _Kt; _Key = long long int; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>]
  find(const _Kt& __x) const
  ^~~~
/usr/include/c++/7/bits/stl_multiset.h:762:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_multiset.h: In substitution of 'template<class _Kt> decltype (std::multiset<long long int>::const_iterator{((const std::multiset<long long int>*)this)->std::multiset<long long int>::_M_t.std::_Rb_tree<long long int, long long int, std::_Identity<long long int>, std::less<long long int>, std::allocator<long long int> >::_M_find_tr(__x)}) std::multiset<long long int>::find<_Kt>(const _Kt&) const [with _Kt = std::_Rb_tree_const_iterator<long long int>]':
santa.cpp:121:62:   required from here
/usr/include/c++/7/bits/stl_multiset.h:762:2: error: no matching function for call to 'std::_Rb_tree<long long int, long long int, std::_Identity<long long int>, std::less<long long int>, std::allocator<long long int> >::_M_find_tr(const std::_Rb_tree_const_iterator<long long int>&) const'
In file included from /usr/include/c++/7/map:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from santa.cpp:3:
/usr/include/c++/7/bits/stl_tree.h:1212:2: note: candidate: template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_find_tr(const _Kt&) [with _Kt = _Kt; _Req = _Req; _Key = long long int; _Val = long long int; _KeyOfValue = std::_Identity<long long int>; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>]
  _M_find_tr(const _Kt& __k)
  ^~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1212:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_tree.h:1209:9: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<long long int>, std::_Rb_tree_const_iterator<long long int>, void>'
         typename _Req =
         ^~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1222:2: note: candidate: template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_find_tr(const _Kt&) const [with _Kt = _Kt; _Req = _Req; _Key = long long int; _Val = long long int; _KeyOfValue = std::_Identity<long long int>; _Compare = std::less<long long int>; _Alloc = std::allocator<long long int>]
  _M_find_tr(const _Kt& __k) const
  ^~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1222:2: note:   template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_tree.h:1219:9: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<long long int>, std::_Rb_tree_const_iterator<long long int>, void>'
         typename _Req =
         ^~~~~~~~
In file included from /usr/include/c++/7/set:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:87,
                 from santa.cpp:3:
/usr/include/c++/7/bits/stl_multiset.h:762:2: error: no matching function for call to 'std::_Rb_tree_const_iterator<long long int>::_Rb_tree_const_iterator(<brace-enclosed initializer list>)'
  find(const _Kt& __x) const
  ^~~~
In file included from /usr/include/c++/7/map:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from santa.cpp:3:
/usr/include/c++/7/bits/stl_tree.h:348:7: note: candidate: std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator(const iterator&) [with _Tp = long long int; std::_Rb_tree_const_iterator<_Tp>::iterator = std::_Rb_tree_iterator<long long int>]
       _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:348:7: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/7/bits/stl_tree.h:345:7: note: candidate: std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator(std::_Rb_tree_const_iterator<_Tp>::_Base_ptr) [with _Tp = long long int; std::_Rb_tree_const_iterator<_Tp>::_Base_ptr = const std::_Rb_tree_node_base*]
       _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:345:7: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/7/bits/stl_tree.h:341:7: note: candidate: std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator() [with _Tp = long long int]
       _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:341:7: note:   candidate expects 0 arguments, 1 provided
/usr/include/c++/7/bits/stl_tree.h:326:12: note: candidate: constexpr std::_Rb_tree_const_iterator<long long int>::_Rb_tree_const_iterator(const std::_Rb_tree_const_iterator<long long int>&)
     struct _Rb_tree_const_iterator
            ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:326:12: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/7/bits/stl_tree.h:326:12: note: candidate: constexpr std::_Rb_tree_const_iterator<long long int>::_Rb_tree_const_iterator(std::_Rb_tree_const_iterator<long long int>&&)
/usr/include/c++/7/bits/stl_tree.h:326:12: note:   conversion of argument 1 would be ill-formed: