Submission #343347

#TimeUsernameProblemLanguageResultExecution timeMemory
343347bigDuckHorses (IOI15_horses)C++14
Compilation error
0 ms0 KiB
#include "horses.h" #include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount ll mod=((ll)1e9)+7; int N; ll exp(ll x, ll e){ if(e==1){ return x%mod; } if(e==0){ return 1; } return (exp(x, e%2)*exp( (x*x)%mod, e/2))%mod; } ll inv(ll x){ return exp(x, mod-2); } ll prod=1ll; multiset<pii> suf; int x[500010], y[500010]; int seg[2000010]; void build_seg(int v, int tl, int tr){ if(tl==tr){ seg[v]=y[tl]; return; } int mid=(tl+tr)>>1ll; build_seg(2*v, tl, mid); build_seg(2*v+1, mid+1, tr); seg[v]=max(seg[2*v], seg[2*v+1]); return; } void update_seg(int v, int tl, int tr, int pos, int x){ if(tl==tr){ seg[v]=x; y[tl]=x; return; } int mid=(tl+tr)>>1ll; if(pos<=mid){ update_seg(2*v, tl, mid, pos, x); } else{ update_seg(2*v+1, mid+1, tr, pos, x); } seg[v]=max(seg[2*v], seg[2*v+1]); return; } int query(int v, int tl, int tr, int l, int r){ if(l>r){ return 0; } if( (tl==l) && (tr==r) ){ return seg[v]; } int mid=(tl+tr)>>1ll; int q1=query(2*v, tl, mid, l, min(r, mid)), q2=query(2*v+1, mid+1, tr, max(l, mid+1), r); return max(q1, q2); } int get_resp(int N){ ll prod2=1ll; ll res=y[N]; auto it=suf.end(); ll lt=N; if(it==suf.begin()){ res=query(1, 1, N, 1, lt); return (res*prod)%mod; } it--; for(;;it--){ ll pos=it->ft, X=it->sc; ll Y=query(1, 1, N, pos, lt); if( ((res*prod2)%mod)<Y ){ //cout<<res<<" "<<((res*prod2)%mod)<<" "<<Y<<" "<<prod<<"\n"; res=(Y*inv(prod2))%mod; } lt=pos-1; prod2*=X; if(prod2>((ll)1e9)){ break; } if(it==suf.begin()){ break; } } if( (prod2<((ll)1e9)) && (lt>0) ){ ll Y=query(1, 1, N, 1, lt); if( ((res*prod2)%mod)<Y ){ res=(Y*inv(prod2))%mod; } } res=(res*prod)%mod; return res; } int init(int n, int X[], int Y[]) { N=n; for(int i=1; i<=N; i++){ x[i]=X[i-1]; y[i]=Y[i-1]; } build_seg(1, 1, N); for(int i=1; i<=N; i++){ prod=(prod*x[i])%mod; } for(int i=1; i<=N; i++){ if(x[i]>1){ suf.insert({i, x[i]}); } } return get_resp(N); } int updateX(int pos, int val) { auto it=suf.find(suf.lower_bound({pos+1, 0})); if( (it!=suf.end()) ){ if( (it->ft)==(pos+1) ){ prod=(prod*inv(it->sc))%mod; suf.erase(it); } } if( (val>0) ){suf.insert({(pos+1), val});} prod=(prod*val)%mod; return get_resp(N); } int updateY(int pos, int val) { update_seg(1, 1, N, pos+1, val); return get_resp(N); }

Compilation message (stderr)

horses.cpp: In function 'void update_seg(int, int, int, int, int)':
horses.cpp:52:54: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   52 | void update_seg(int v, int tl, int tr, int pos, int x){
      |                                                      ^
horses.cpp:36:5: note: shadowed declaration is here
   36 | int x[500010], y[500010];
      |     ^
horses.cpp: In function 'int get_resp(int)':
horses.cpp:86:19: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   86 | int get_resp(int N){
      |                   ^
horses.cpp:15:5: note: shadowed declaration is here
   15 | int N;
      |     ^
horses.cpp:93:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |         res=query(1, 1, N, 1, lt);
      |                               ^~
horses.cpp:94:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   94 |         return (res*prod)%mod;
      |                ~~~~~~~~~~^~~~
horses.cpp:99:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |         ll Y=query(1, 1, N, pos, lt);
      |                             ^~~
horses.cpp:99:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |         ll Y=query(1, 1, N, pos, lt);
      |                                  ^~
horses.cpp:115:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |         ll Y=query(1, 1, N, 1, lt);
      |                                ^~
horses.cpp:122:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |     return res;
      |            ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:147:49: error: no matching function for call to 'std::multiset<std::pair<int, int> >::find(std::multiset<std::pair<int, int> >::iterator)'
  147 |     auto it=suf.find(suf.lower_bound({pos+1, 0}));
      |                                                 ^
In file included from /usr/include/c++/9/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
                 from horses.cpp:3:
/usr/include/c++/9/bits/stl_multiset.h:775:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::find(const key_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >; std::multiset<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  775 |       find(const key_type& __x)
      |       ^~~~
/usr/include/c++/9/bits/stl_multiset.h:775:28: note:   no known conversion for argument 1 from 'std::multiset<std::pair<int, int> >::iterator' {aka 'std::_Rb_tree_const_iterator<std::pair<int, int> >'} to 'const key_type&' {aka 'const std::pair<int, int>&'}
  775 |       find(const key_type& __x)
      |            ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_multiset.h:779:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::const_iterator std::multiset<_Key, _Compare, _Alloc>::find(const key_type&) const [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >; std::multiset<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  779 |       find(const key_type& __x) const
      |       ^~~~
/usr/include/c++/9/bits/stl_multiset.h:779:28: note:   no known conversion for argument 1 from 'std::multiset<std::pair<int, int> >::iterator' {aka 'std::_Rb_tree_const_iterator<std::pair<int, int> >'} to 'const key_type&' {aka 'const std::pair<int, int>&'}
  779 |       find(const key_type& __x) const
      |            ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_multiset.h:785: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 = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  785 |  find(const _Kt& __x)
      |  ^~~~
/usr/include/c++/9/bits/stl_multiset.h:785:2: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_multiset.h: In substitution of 'template<class _Kt> decltype (std::multiset<std::pair<int, int> >::iterator{((std::multiset<std::pair<int, int> >*)this)->std::multiset<std::pair<int, int> >::_M_t.std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_M_find_tr(__x)}) std::multiset<std::pair<int, int> >::find<_Kt>(const _Kt&) [with _Kt = std::_Rb_tree_const_iterator<std::pair<int, int> >]':
horses.cpp:147:49:   required from here
/usr/include/c++/9/bits/stl_multiset.h:785:2: error: no matching function for call to 'std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_M_find_tr(const std::_Rb_tree_const_iterator<std::pair<int, int> >&)'
In file included from /usr/include/c++/9/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from horses.cpp:3:
/usr/include/c++/9/bits/stl_tree.h:1306: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 = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
 1306 |  _M_find_tr(const _Kt& __k)
      |  ^~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:1306:2: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_tree.h: In substitution of 'template<class _Cmp, class _SfinaeType> using __has_is_transparent_t = typename std::__has_is_transparent<_Cmp, _SfinaeType>::type [with _Cmp = std::less<std::pair<int, int> >; _SfinaeType = std::_Rb_tree_const_iterator<std::pair<int, int> >]':
/usr/include/c++/9/bits/stl_tree.h:1304:9:   required by substitution of 'template<class _Kt> decltype (std::multiset<std::pair<int, int> >::iterator{((std::multiset<std::pair<int, int> >*)this)->std::multiset<std::pair<int, int> >::_M_t.std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_M_find_tr(__x)}) std::multiset<std::pair<int, int> >::find<_Kt>(const _Kt&) [with _Kt = std::_Rb_tree_const_iterator<std::pair<int, int> >]'
horses.cpp:147:49:   required from here
/usr/include/c++/9/bits/stl_tree.h:425:11: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<std::pair<int, int> >, std::_Rb_tree_const_iterator<std::pair<int, int> >, void>'
  425 |     using __has_is_transparent_t
      |           ^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_multiset.h: In substitution of 'template<class _Kt> decltype (std::multiset<std::pair<int, int> >::iterator{((std::multiset<std::pair<int, int> >*)this)->std::multiset<std::pair<int, int> >::_M_t.std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_M_find_tr(__x)}) std::multiset<std::pair<int, int> >::find<_Kt>(const _Kt&) [with _Kt = std::_Rb_tree_const_iterator<std::pair<int, int> >]':
horses.cpp:147:49:   required from here
/usr/include/c++/9/bits/stl_tree.h:1315: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 = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
 1315 |  _M_find_tr(const _Kt& __k) const
      |  ^~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:1315:2: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/9/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
                 from horses.cpp:3:
/usr/include/c++/9/bits/stl_multiset.h:785:2: error: no matching function for call to 'std::_Rb_tree_const_iterator<std::pair<int, int> >::_Rb_tree_const_iterator(<brace-enclosed initializer list>)'
  785 |  find(const _Kt& __x)
      |  ^~~~
In file included from /usr/include/c++/9/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from horses.cpp:3:
/usr/include/c++/9/bits/stl_tree.h:348:7: note: candidate: 'std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator(const iterator&) [with _Tp = std::pair<int, int>; std::_Rb_tree_const_iterator<_Tp>::iterator = std::_Rb_tree_iterator<std::pair<int, int> >]'
  348 |       _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:348:7: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/9/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 = std::pair<int, int>; std::_Rb_tree_const_iterator<_Tp>::_Base_ptr = const std::_Rb_tree_node_base*]'
  345 |       _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:345:7: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/9/bits/stl_tree.h:341:7: note: candidate: 'std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator() [with _Tp = std::pair<int, int>]'
  341 |       _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:341:7: note:   candidate expects 0 arguments, 1 provided
/usr/include/c++/9/bits/stl_tree.h:326:12: note: candidate: 'constexpr std::_Rb_tree_const_iterator<std::pair<int, int> >::_Rb_tree_const_iterator(const std::_Rb_tree_const_iterator<std::pair<int, int> >&)'
  326 |     struct _Rb_tree_const_iterator
      |            ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:326:12: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/9/bits/stl_tree.h:326:12: note: candidate: 'constexpr std::_Rb_tree_const_iterator<std::pair<int, int> >::_Rb_tree_const_iterator(std::_Rb_tree_const_iterator<std::pair<int, int> >&&)'
/usr/include/c++/9/bits/stl_tree.h:326:12: note:   conversion of argument 1 would be ill-formed:
In file included from /usr/include/c++/9/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
                 from horses.cpp:3:
/usr/include/c++/9/bits/stl_multiset.h:791: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 = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  791 |  find(const _Kt& __x) const
      |  ^~~~
/usr/include/c++/9/bits/stl_multiset.h:791:2: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_multiset.h: In substitution of 'template<class _Kt> decltype (std::multiset<std::pair<int, int> >::const_iterator{((const std::multiset<std::pair<int, int> >*)this)->std::multiset<std::pair<int, int> >::_M_t.std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_M_find_tr(__x)}) std::multiset<std::pair<int, int> >::find<_Kt>(const _Kt&) const [with _Kt = std::_Rb_tree_const_iterator<std::pair<int, int> >]':
horses.cpp:147:49:   required from here
/usr/include/c++/9/bits/stl_multiset.h:791:2: error: no matching function for call to 'std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::_M_find_tr(const std::_Rb_tree_const_iterator<std::pair<int, int> >&) const'
In file included from /usr/include/c++/9/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from horses.cpp:3:
/usr/include/c++/9/bits/stl_tree.h:1306: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 = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
 1306 |  _M_find_tr(const _Kt& __k)
      |  ^~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:1306:2: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/stl_tree.h:1315: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 = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
 1315 |  _M_find_tr(const _Kt& __k) const
      |  ^~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:1315:2: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/9/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
                 from horses.cpp:3:
/usr/include/c++/9/bits/stl_multiset.h:791:2: error: no matching function for call to 'std::_Rb_tree_const_iterator<std::pair<int, int> >::_Rb_tree_const_iterator(<brace-enclosed initializer list>)'
  791 |  find(const _Kt& __x) const
      |  ^~~~
In file included from /usr/include/c++/9/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from horses.cpp:3:
/usr/include/c++/9/bits/stl_tree.h:348:7: note: candidate: 'std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator(const iterator&) [with _Tp = std::pair<int, int>; std::_Rb_tree_const_iterator<_Tp>::iterator = std::_Rb_tree_iterator<std::pair<int, int> >]'
  348 |       _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:348:7: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/9/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 = std::pair<int, int>; std::_Rb_tree_const_iterator<_Tp>::_Base_ptr = const std::_Rb_tree_node_base*]'
  345 |       _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:345:7: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/9/bits/stl_tree.h:341:7: note: candidate: 'std::_Rb_tree_const_iterator<_Tp>::_Rb_tree_const_iterator() [with _Tp = std::pair<int, int>]'
  341 |       _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:341:7: note:   candidate expects 0 arguments, 1 provided
/usr/include/c++/9/bits/stl_tree.h:326:12: note: candidate: 'constexpr std::_Rb_tree_const_iterator<std::pair<int, int> >::_Rb_tree_const_iterator(const std::_Rb_tree_const_iterator<std::pair<int, int> >&)'
  326 |     struct _Rb_tree_const_iterator
      |            ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_tree.h:326:12: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/9/bits/stl_tree.h:326:12: note: candidate: 'constexpr std::_Rb_tree_const_iterator<std::pair<int, int> >::_Rb_tree_const_iterator(std::_Rb_tree_const_iterator<std::pair<int, int> >&&)'
/usr/include/c++/9/bits/stl_tree.h:326:12: note:   conversion of argument 1 would be ill-formed: