Submission #290288

#TimeUsernameProblemLanguageResultExecution timeMemory
290288eohomegrownappsHoliday (IOI14_holiday)C++14
Compilation error
0 ms0 KiB
#include "holiday.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<ll> ind2coord; struct Node{ ll s,e,m; ll num = 0; ll sum = 0; ll val = 0; Node *l, *r; Node(ll _s, ll _e, bool children = true){ s=_s;e=_e; //cout<<"node "<<s<<' '<<e<<endl; m=(s+e)/2; if (s==e){ val=ind2coord[s]; return; } if (children){ l = new Node(s,m,true); r = new Node(m+1,e,true); } } ll query(ll k){ if (k<0){return 0;} //k largest elements if (s==e){ //assert(k<=num); return min(k,num)*val; } if (r->num>=k){ return r->query(k); } else { return l->query(k-r->num) + r->sum; } } Node* update(ll ind, bool on){ //cout<<s<<' '<<e<<endl; Node* ans = new Node(s,e,false); if (s==e){ if (on){ ans->num = num+1; } else { ans->num = max(0, num-1); } ans->sum = ans->val * ans->num; return ans; } if (ind<=m){ //cout<<"left"<<endl; ans->l = l->update(ind,on); ans->r = r; } else { //cout<<"right"<<endl; ans->l = l; ans->r = r->update(ind,on); } ans->num = ans->l->num + ans->r->num; ans->sum = ans->l->sum + ans->r->sum; return ans; } }; struct PersistentSet{ vector<Node*> nodes; PersistentSet(){ //cout<<"ic "<<ind2coord.size()<<endl; nodes.push_back(new Node(0,ind2coord.size()-1)); } void insert(ll val){ ll ind = lower_bound(ind2coord.begin(), ind2coord.end(), val)-ind2coord.begin(); nodes.push_back(nodes.back()->update(ind,true)); } ll query(ll k, ll t){ return nodes[t]->query(k); } void clear(){ nodes.clear(); nodes.push_back(new Node(0,ind2coord.size()-1)); } }; vector<ll> rvals; vector<ll> lvals; vector<ll> rvals2; vector<ll> lvals2; PersistentSet *ps; void dnc(ll s, ll e, ll x, ll y, vector<ll> &vals, bool thereandback){ //cout<<s<<' '<<e<<' '<<x<<' '<<y<<endl; // query s,e knowing optimum lies within range x,y ll m = (s+e)/2; ll mx = -1; ll mxind = -1; for (ll v = x; v<=y; v++){ ll test = ps->query(m-(thereandback?2*v:v),v+1); if (test>mx){ mx=test; mxind=v; } } vals[m]=mx; if (s<m){ dnc(s,m-1,x,mxind,vals,thereandback); } if (m<e){ dnc(m+1,e,mxind,y,vals,thereandback); } } ll findMaxAttraction(int n, int start, int d, int attraction[]) { ind2coord.resize(n); for (ll i = 0; i<n; i++){ ind2coord[i]=attraction[i]; } sort(ind2coord.begin(),ind2coord.end()); ind2coord.erase(unique(ind2coord.begin(),ind2coord.end()),ind2coord.end()); //cout<<ind2coord.size()<<endl; ps = new PersistentSet(); ps->clear(); for (ll i = start; i<n; i++){ ps->insert(attraction[i]); } lvals2.resize((n-start)*4); dnc(0,(n-start)*4-1,0,n-1-start,lvals2,true); /*for (ll i : lvals2){ cout<<i<<' '; }cout<<endl;*/ ps->clear(); for (ll i = start+1; i<n; i++){ ps->insert(attraction[i]); } lvals.resize((n-(start+1))*2); if (start+1<n){ dnc(0,(n-(start+1))*2-1,0,n-1-(start+1),lvals,false); } /*for (ll i : lvals){ cout<<i<<' '; }cout<<endl;*/ ps->clear(); for (ll i = start; i>=0; i--){ ps->insert(attraction[i]); } rvals2.resize((start+1)*4); dnc(0,(start+1)*4-1,0,start,rvals2,true); /*for (ll i : rvals2){ cout<<i<<' '; }cout<<endl;*/ ps->clear(); for (ll i = start-1; i>=0; i--){ ps->insert(attraction[i]); } rvals.resize((start)*2); if (start-1>=0){ dnc(0,(start)*2-1,0,start-1,rvals,false); } /*for (ll i : rvals){ cout<<i<<' '; }cout<<endl;*/ //go left then go right ll mx = 0; for (ll i = 0; i<d-1; i++){ // i left, d right if (lvals2.size()>i&&rvals.size()>d-1-i) mx=max(mx,lvals2[i]+rvals[d-1-i]); if (rvals2.size()>i&&lvals.size()>d-1-i) mx=max(mx,rvals2[i]+lvals[d-i-1]); } return mx; }

Compilation message (stderr)

holiday.cpp: In member function 'Node* Node::update(ll, bool)':
holiday.cpp:50:40: error: no matching function for call to 'max(int, ll)'
   50 |                 ans->num = max(0, num-1);
      |                                        ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from holiday.cpp:2:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
holiday.cpp:50:40: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   50 |                 ans->num = max(0, num-1);
      |                                        ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from holiday.cpp:2:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
holiday.cpp:50:40: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   50 |                 ans->num = max(0, num-1);
      |                                        ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from holiday.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
holiday.cpp:50:40: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   50 |                 ans->num = max(0, num-1);
      |                                        ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from holiday.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
holiday.cpp:50:40: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   50 |                 ans->num = max(0, num-1);
      |                                        ^
holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:185:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  185 |         if (lvals2.size()>i&&rvals.size()>d-1-i)
      |             ~~~~~~~~~~~~~^~
holiday.cpp:185:42: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  185 |         if (lvals2.size()>i&&rvals.size()>d-1-i)
      |                              ~~~~~~~~~~~~^~~~~~
holiday.cpp:187:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  187 |         if (rvals2.size()>i&&lvals.size()>d-1-i)
      |             ~~~~~~~~~~~~~^~
holiday.cpp:187:42: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  187 |         if (rvals2.size()>i&&lvals.size()>d-1-i)
      |                              ~~~~~~~~~~~~^~~~~~