Submission #1011468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011468		User0069	Holiday (IOI14_holiday)	C++17	Compilation error	0 ms	0 KiB

holiday

#include<bits/stdc++.h>
#include<holiday.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e5+3;
const int mod=1e9+7;
const int INF=1e9+1;
int n,m,k,x,y,a[maxn],cur,S,opt[maxn];
long long dp[maxn][3][2];
vector<int> v;
struct node
{
    vector<int> a;
    vector<long long> pfs;
    int l,r;
}ST[maxn*30];
void cons(int id,vector<int> v,int lval,int rval)
{
    if(v.size()==0) return;
    int mid=(lval+rval)/2;
    vector<int> s[2];
    ST[id].a.push_back(0);
    ST[id].pfs.push_back(0);
    for(int i:v)
    {
        int cc=ST[id].a.back()+(a[i]>mid);
        ST[id].a.push_back(cc);
        s[a[i]>mid].push_back(i);
        cc=ST[id].pfs.back()+(a[i]>mid)*a[i];
        ST[id].pfs.push_back(cc);
    }
    v.clear();
    if(rval==lval) return;
    if(s[0].size()) cons(ST[id].l=++cur,s[0],lval,mid);
    if(s[1].size()) cons(ST[id].r=++cur,s[1],mid+1,rval);
}
int get(int id,int k,int l,int r,int lval,int rval)
{
    if(id==0||ST[id].a.size()<=1||k<=0) return 0;
    if(lval==rval)
    {
        return min(k,(int)ST[id].a.size())*lval;
    }
    int mid=(lval+rval)/2;
    int s1=ST[id].a[l-1];
    int s2=ST[id].a[r];
    if(s2-s1>k)
    {
        return get(ST[id].r,k,s1+1,s2,mid+1,rval);
    }
    else
    {
        int cnt=ST[id].pfs[r]-ST[id].pfs[l-1];
        return cnt+get(ST[id].l,k-(s2-s1),l-s1,r-s2,lval,mid);
    }
}
void dnc(int l,int r,int optl,int optr,int rev,int jump)
{
    if(l>r) return;
    int mid=(l+r)/2;
    opt[mid]=optl,dp[mid][jump][rev]=0;
    for(int i=optl;i<=optr;i++)
    {
        if(!rev)
        {
            int dd=i-S;
            int cc=get(1,mid-dd*jump,S+1,i,1,1e9);
            if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i;
        }
        if(rev)
        {
            int dd=S-i;
            int cc=get(1,mid-dd*jump,i,S-1,1,1e9);
            if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i;
        }

    }
    if(l==r) return;
    if(!rev)
    {
        dnc(l,mid-1,optl,opt[mid],rev,jump);
        dnc(mid+1,r,opt[mid],optr,rev,jump);
    }
    if(rev)
    {
        dnc(l,mid-1,opt[mid],optr,rev,jump);
        dnc(mid+1,r,optl,opt[mid],rev,jump);
    }
}
long long findMaxAttraction(int32_t n,int32_t start,int32_t d,int32_t b[])
{
    for(int i=1;i<=n;i++) v.push_back(i);
    for(int i=0;i<n;i++) a[i+1]=b[i];
    cons(1,v,1,1e9);
    S=start;
    dnc(1,d,1,S-1,1,1);
    dnc(1,d,1,S-1,1,2);
    dnc(1,d,S+1,n,0,1);
    dnc(1,d,S+1,n,0,2);
    int ans=0;
    for(int i=0;i<=d;i++)
    {
        ans=max(dp[i][1][0]+dp[d-i][2][1],ans);
        ans=max(dp[i][1][1]+dp[d-i][2][0],ans);
        if(i<d)
        {
            ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]);
            ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]);
        }
    }
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int32_t, int32_t, int32_t, int32_t*)':
holiday.cpp:114:46: error: no matching function for call to 'max(long long int, int&)'
  114 |         ans=max(dp[i][1][0]+dp[d-i][2][1],ans);
      |                                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
holiday.cpp:114:46: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  114 |         ans=max(dp[i][1][0]+dp[d-i][2][1],ans);
      |                                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
holiday.cpp:114:46: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  114 |         ans=max(dp[i][1][0]+dp[d-i][2][1],ans);
      |                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
holiday.cpp:114:46: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  114 |         ans=max(dp[i][1][0]+dp[d-i][2][1],ans);
      |                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
holiday.cpp:114:46: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  114 |         ans=max(dp[i][1][0]+dp[d-i][2][1],ans);
      |                                              ^
holiday.cpp:115:46: error: no matching function for call to 'max(long long int, int&)'
  115 |         ans=max(dp[i][1][1]+dp[d-i][2][0],ans);
      |                                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
holiday.cpp:115:46: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  115 |         ans=max(dp[i][1][1]+dp[d-i][2][0],ans);
      |                                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
holiday.cpp:115:46: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  115 |         ans=max(dp[i][1][1]+dp[d-i][2][0],ans);
      |                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
holiday.cpp:115:46: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  115 |         ans=max(dp[i][1][1]+dp[d-i][2][0],ans);
      |                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
holiday.cpp:115:46: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  115 |         ans=max(dp[i][1][1]+dp[d-i][2][0],ans);
      |                                              ^
holiday.cpp:118:57: error: no matching function for call to 'max(int&, long long int)'
  118 |             ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]);
      |                                                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
holiday.cpp:118:57: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  118 |             ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]);
      |                                                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
holiday.cpp:118:57: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  118 |             ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]);
      |                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
holiday.cpp:118:57: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  118 |             ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]);
      |                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
holiday.cpp:118:57: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  118 |             ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]);
      |                                                         ^
holiday.cpp:119:57: error: no matching function for call to 'max(int&, long long int)'
  119 |             ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]);
      |                                                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
holiday.cpp:119:57: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  119 |             ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]);
      |                                                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
holiday.cpp:119:57: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  119 |             ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]);
      |                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
holiday.cpp:119:57: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  119 |             ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]);
      |                                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from holiday.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
holiday.cpp:119:57: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  119 |             ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]);
      |                                                         ^