Submission #1093313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093313		asli_bg	Untitled (POI11_rot)	C++11	Compilation error	0 ms	0 KiB

Main

#pragma GCC optimize("O3,unroll-loops")

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

#define int long long

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> inset;
 
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
 
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;}
#define sp <<" "<<
#define mid (l+r)/2
#define endl '\n'
 
#define DEBUG(X) {cout<<#X<<' '<<(X)<<endl;}
 
#define carp(x,y) ((x%MOD)*(y%MOD))%MOD
#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
 
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
 
const int MAXN=2e5+5;
const int INF=1e9+7;
const int MOD=1e9+7;

int n;
//int adj[MAXN][2];
int t[MAXN*4];

void oku(int nd){
    int el;
    cin>>el;
    if(el!=0){
        t[nd]=el;
        return;
    }
    t[nd]=-1;
    oku(nd*2);
    oku(nd*2+1);
}

int inv[4*MAXN];
inset s[MAXN];

void merge(int nd,int sol,int sag){
    //cout<<"here"<<endl;
    
    if(s[sol].size()<s[sag].size()) swap(sol,sag);
    s[nd]=s[sol];
    inv[nd]+=inv[sol];

    if(t[nd]!=-1) s[sag].insert(t[nd]);

    //cont(s[sol]);
    //cont(s[sag]);

    for(auto el:s[sag]){
        inv[nd]=s[nd].size()-s[nd].order_of_key(el);
        s[nd].insert(el);
    }
}

void dfs(int nd,int ata){ 
    if(t[nd]==0) return;
    dfs(nd*2,ata);
    dfs(nd*2+1,ata);
    merge(nd,nd*2,nd*2+1);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;

    oku(1);
    dfs(1,0);

    cout<<inv[1]<<endl;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/ext/pb_ds/detail/type_utils.hpp:47,
                 from /usr/include/c++/10/ext/pb_ds/tag_and_trait.hpp:46,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:46,
                 from rot.cpp:8:
/usr/include/c++/10/tr1/type_traits:121:3: error: redefinition of 'struct std::tr1::__is_integral_helper<long long int>'
  121 |   _DEFINE_SPEC(0, __is_integral_helper, long long, true)
      |   ^~~~~~~~~~~~
/usr/include/c++/10/tr1/type_traits:117:3: note: previous definition of 'struct std::tr1::__is_integral_helper<long long int>'
  117 |   _DEFINE_SPEC(0, __is_integral_helper, int, true)
      |   ^~~~~~~~~~~~
/usr/include/c++/10/tr1/type_traits:122:3: error: redefinition of 'struct std::tr1::__is_integral_helper<long long unsigned int>'
  122 |   _DEFINE_SPEC(0, __is_integral_helper, unsigned long long, true)
      |   ^~~~~~~~~~~~
/usr/include/c++/10/tr1/type_traits:118:3: note: previous definition of 'struct std::tr1::__is_integral_helper<long long unsigned int>'
  118 |   _DEFINE_SPEC(0, __is_integral_helper, unsigned int, true)
      |   ^~~~~~~~~~~~
/usr/include/c++/10/tr1/type_traits:549:3: error: redefinition of 'struct std::tr1::__is_signed_helper<long long int>'
  549 |   _DEFINE_SPEC(0, __is_signed_helper, long long, true)
      |   ^~~~~~~~~~~~
/usr/include/c++/10/tr1/type_traits:547:3: note: previous definition of 'struct std::tr1::__is_signed_helper<long long int>'
  547 |   _DEFINE_SPEC(0, __is_signed_helper, int, true)
      |   ^~~~~~~~~~~~
/usr/include/c++/10/tr1/type_traits:564:3: error: redefinition of 'struct std::tr1::__is_unsigned_helper<long long unsigned int>'
  564 |   _DEFINE_SPEC(0, __is_unsigned_helper, unsigned long long, true)
      |   ^~~~~~~~~~~~
/usr/include/c++/10/tr1/type_traits:562:3: note: previous definition of 'struct std::tr1::__is_unsigned_helper<long long unsigned int>'
  562 |   _DEFINE_SPEC(0, __is_unsigned_helper, unsigned int, true)
      |   ^~~~~~~~~~~~
In file included from /usr/include/c++/10/tr1/functional:42,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:51,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from rot.cpp:8:
/usr/include/c++/10/tr1/functional_hash.h:75:3: error: redefinition of 'std::size_t std::tr1::hash<_Tp>::operator()(_Tp) const [with _Tp = long long int; std::size_t = long unsigned int]'
   75 |   _TR1_hashtable_define_trivial_hash(long long);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/tr1/functional_hash.h:73:3: note: 'std::size_t std::tr1::hash<_Tp>::operator()(_Tp) const [with _Tp = long long int; std::size_t = long unsigned int]' previously declared here
   73 |   _TR1_hashtable_define_trivial_hash(int);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/tr1/functional_hash.h:79:3: error: redefinition of 'std::size_t std::tr1::hash<_Tp>::operator()(_Tp) const [with _Tp = long long unsigned int; std::size_t = long unsigned int]'
   79 |   _TR1_hashtable_define_trivial_hash(unsigned long long);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/tr1/functional_hash.h:77:3: note: 'std::size_t std::tr1::hash<_Tp>::operator()(_Tp) const [with _Tp = long long unsigned int; std::size_t = long unsigned int]' previously declared here
   77 |   _TR1_hashtable_define_trivial_hash(unsigned int);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
                 from rot.cpp:3:
/usr/include/c++/10/functional:209:16: error: template parameter 'int _Num'
  209 |   template<int _Num> struct _Placeholder { };
      |                ^~~~
In file included from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:51,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from rot.cpp:8:
/usr/include/c++/10/tr1/functional:53:24: note: redeclared here as 'long long int <anonymous>'
   53 |   template<int> struct _Placeholder;
      |                        ^~~~~~~~~~~~
In file included from /usr/include/c++/10/ext/pb_ds/detail/bin_search_tree_/traits.hpp:44,
                 from /usr/include/c++/10/ext/pb_ds/detail/branch_policy/traits.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:49,
                 from rot.cpp:8:
/usr/include/c++/10/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp: In instantiation of 'class __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >':
/usr/include/c++/10/bits/stl_iterator_base_types.h:177:12:   recursively required by substitution of 'template<class _Iterator> struct std::__iterator_traits<_Iterator, std::__void_t<typename _Iterator::iterator_category, typename _Iterator::value_type, typename _Iterator::difference_type, typename _Iterator::pointer, typename _Iterator::reference> > [with _Iterator = __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >]'
/usr/include/c++/10/bits/stl_iterator_base_types.h:177:12:   required from 'struct std::iterator_traits<__gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> > >'
/usr/include/c++/10/ext/pb_ds/detail/branch_policy/branch_policy.hpp:93:68:   required from 'struct __gnu_pbds::detail::branch_policy<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, std::allocator<char> >, std::allocator<char> >'
/usr/include/c++/10/ext/pb_ds/tree_policy.hpp:64:9:   required from 'class __gnu_pbds::tree_order_statistics_node_update<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, std::allocator<char> >, std::less<long long int>, std::allocator<char> >'
/usr/include/c++/10/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp:99:11:   required from 'class __gnu_pbds::detail::bin_search_tree_set<long long int, __gnu_pbds::null_type, std::less<long long int>, __gnu_pbds::detail::tree_traits<long long int, __gnu_pbds::null_type, std::less<long long int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >'
/usr/include/c++/10/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp:84:11:   required from 'class __gnu_pbds::detail::rb_tree_set<long long int, __gnu_pbds::null_type, std::less<long long int>, __gnu_pbds::detail::tree_traits<long long int, __gnu_pbds::null_type, std::less<long long int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >'
/usr/include/c++/10/ext/pb_ds/assoc_container.hpp:555:9:   required from 'class __gnu_pbds::basic_branch<long long int, __gnu_pbds::null_type, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, std::allocator<char> >, std::less<long long int>, std::allocator<char> >, __gnu_cxx::typelist::node<__gnu_cxx::typelist::chain<std::less<long long int>, __gnu_cxx::typelist::chain<__gnu_pbds::detail::tree_traits<long long int, __gnu_pbds::null_type, std::less<long long int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, __gnu_cxx::typelist::null_type> > >, std::allocator<char> >'
/usr/include/c++/10/ext/pb_ds/assoc_container.hpp:635:9:   required from 'class __gnu_pbds::tree<long long int, __gnu_pbds::null_type, std::less<long long int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>'
rot.cpp:58:13:   required from here
/usr/include/c++/10/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp:181:7: error: postfix '__gnu_pbds::detail::bin_search_tree_const_it_<Node_Pointer, Value_Type, Pointer, Const_Pointer, Reference, Const_Reference, Is_Forward_Iterator, _Alloc> __gnu_pbds::detail::bin_search_tree_const_it_<Node_Pointer, Value_Type, Pointer, Const_Pointer, Reference, Const_Reference, Is_Forward_Iterator, _Alloc>::operator++(long long int) [with Node_Pointer = __gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*; Value_Type = long long int; Pointer = long long int*; Const_Pointer = const long long int*; Reference = long long int&; Const_Reference = const long long int&; bool Is_Forward_Iterator = true; _Alloc = std::allocator<char>]' must have 'int' as its argument
  181 |       operator++(int)
      |       ^~~~~~~~
/usr/include/c++/10/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp:196:7: error: postfix '__gnu_pbds::detail::bin_search_tree_const_it_<Node_Pointer, Value_Type, Pointer, Const_Pointer, Reference, Const_Reference, Is_Forward_Iterator, _Alloc> __gnu_pbds::detail::bin_search_tree_const_it_<Node_Pointer, Value_Type, Pointer, Const_Pointer, Reference, Const_Reference, Is_Forward_Iterator, _Alloc>::operator--(long long int) [with Node_Pointer = __gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*; Value_Type = long long int; Pointer = long long int*; Const_Pointer = const long long int*; Reference = long long int&; Const_Reference = const long long int&; bool Is_Forward_Iterator = true; _Alloc = std::allocator<char>]' must have 'int' as its argument
  196 |       operator--(int)
      |       ^~~~~~~~
/usr/include/c++/10/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp: In instantiation of 'class __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, false, std::allocator<char> >':
/usr/include/c++/10/type_traits:1085:30:   required from 'struct std::__is_copy_assignable_impl<__gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, true>'
/usr/include/c++/10/type_traits:1090:12:   required from 'struct std::is_copy_assignable<__gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> > >'
/usr/include/c++/10/type_traits:138:12:   required from 'struct std::__and_<std::is_copy_assignable<__gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> > >, std::is_copy_assignable<bool> >'
/usr/include/c++/10/bits/stl_pair.h:390:7:   required from 'struct std::pair<__gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*, long long int, long long int*, const long long int*, long long int&, const long long int&, true, std::allocator<char> >, bool>'
rot.cpp:67:38:   required from here
/usr/include/c++/10/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp:181:7: error: postfix '__gnu_pbds::detail::bin_search_tree_const_it_<Node_Pointer, Value_Type, Pointer, Const_Pointer, Reference, Const_Reference, Is_Forward_Iterator, _Alloc> __gnu_pbds::detail::bin_search_tree_const_it_<Node_Pointer, Value_Type, Pointer, Const_Pointer, Reference, Const_Reference, Is_Forward_Iterator, _Alloc>::operator++(long long int) [with Node_Pointer = __gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*; Value_Type = long long int; Pointer = long long int*; Const_Pointer = const long long int*; Reference = long long int&; Const_Reference = const long long int&; bool Is_Forward_Iterator = false; _Alloc = std::allocator<char>]' must have 'int' as its argument
  181 |       operator++(int)
      |       ^~~~~~~~
/usr/include/c++/10/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp:196:7: error: postfix '__gnu_pbds::detail::bin_search_tree_const_it_<Node_Pointer, Value_Type, Pointer, Const_Pointer, Reference, Const_Reference, Is_Forward_Iterator, _Alloc> __gnu_pbds::detail::bin_search_tree_const_it_<Node_Pointer, Value_Type, Pointer, Const_Pointer, Reference, Const_Reference, Is_Forward_Iterator, _Alloc>::operator--(long long int) [with Node_Pointer = __gnu_pbds::detail::rb_tree_node_<long long int, long unsigned int, std::allocator<char> >*; Value_Type = long long int; Pointer = long long int*; Const_Pointer = const long long int*; Reference = long long int&; Const_Reference = const long long int&; bool Is_Forward_Iterator = false; _Alloc = std::allocator<char>]' must have 'int' as its argument
  196 |       operator--(int)
      |       ^~~~~~~~