Submission #46609

#	Time	Username	Problem	Language	Result	Execution time	Memory
46609		dqhungdl	Split the sequence (APIO14_sequence)	C++17	Compilation error	0 ms	0 KiB

sequence

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

struct data
{
    int64_t a,b,id;
};

typedef pair<int64_t,int64_t> ii;
int64_t n,k,top,point64_ter,a[100005],f[100005][205],Trace[100005][205];
data S[100005];

bool Check(data x1,data x2,data x3)
{
    ///int64_tersection(x1,x2)=(x1.b-x2.b)/(x2.a-x1.a)
    ///int64_tersection(x1,x3)=(x1.b-x3.b)/(x3.a-x1.a)
    return (x1.b-x3.b)*(x2.a-x1.a)<(x1.b-x2.b)*(x3.a-x1.a);
}

void Update(int64_t x,int64_t y,int64_t id)
{
    while(top>=2&&Check(S[top-1],S[top],{x,y,id})==true)
        top--;
    S[++top]={x,y,id};
}

ii Query(int64_t x)
{
    point64_ter=min(point64_ter,top);
    while(point64_ter<top&&S[point64_ter+1].a*x+S[point64_ter+1].b<S[point64_ter].a*x+S[point64_ter].b)
        point64_ter++;
    return ii(S[point64_ter].a*x+S[point64_ter].b,S[point64_ter].id);
}

void Process(int64_t kk)
{
    top=0;
    point64_ter=1;
    Update(0,0,0);
    for(int64_t i=1;i<=n;i++)
    {
        ii tmp=Query(a[i]);
        f[i][kk]=-tmp.first;
        Trace[i][kk]=tmp.second;
        Update(-a[i],a[i]*a[i]-f[i][kk-1],i);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n>>k;
    for(int64_t i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }
    for(int64_t i=1;i<=k;i++)
        Process(i);
    cout<<f[n][k]<<"\n";
    while(k>0)
    {
        n=Trace[n][k];
        k--;
        cout<<n<<' ';
    }
}

Compilation message (stderr)

sequence.cpp:11:1: error: reference to 'data' is ambiguous
 data S[100005];
 ^~~~
sequence.cpp:4:8: note: candidates are: struct data
 struct data
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from sequence.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
sequence.cpp:13:12: error: reference to 'data' is ambiguous
 bool Check(data x1,data x2,data x3)
            ^~~~
sequence.cpp:4:8: note: candidates are: struct data
 struct data
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from sequence.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
sequence.cpp:13:20: error: reference to 'data' is ambiguous
 bool Check(data x1,data x2,data x3)
                    ^~~~
sequence.cpp:4:8: note: candidates are: struct data
 struct data
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from sequence.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
sequence.cpp:13:28: error: reference to 'data' is ambiguous
 bool Check(data x1,data x2,data x3)
                            ^~~~
sequence.cpp:4:8: note: candidates are: struct data
 struct data
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from sequence.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
sequence.cpp:13:35: error: expression list treated as compound expression in initializer [-fpermissive]
 bool Check(data x1,data x2,data x3)
                                   ^
sequence.cpp: In function 'void Update(int64_t, int64_t, int64_t)':
sequence.cpp:22:25: error: 'S' was not declared in this scope
     while(top>=2&&Check(S[top-1],S[top],{x,y,id})==true)
                         ^
sequence.cpp:22:49: error: 'Check' cannot be used as a function
     while(top>=2&&Check(S[top-1],S[top],{x,y,id})==true)
                                                 ^
sequence.cpp:24:5: error: 'S' was not declared in this scope
     S[++top]={x,y,id};
     ^
sequence.cpp: In function 'ii Query(int64_t)':
sequence.cpp:30:28: error: 'S' was not declared in this scope
     while(point64_ter<top&&S[point64_ter+1].a*x+S[point64_ter+1].b<S[point64_ter].a*x+S[point64_ter].b)
                            ^
sequence.cpp:32:15: error: 'S' was not declared in this scope
     return ii(S[point64_ter].a*x+S[point64_ter].b,S[point64_ter].id);
               ^