Submission #876904

#	Time	Username	Problem	Language	Result	Execution time	Memory
876904		arnold518	Split the sequence (APIO14_sequence)	C++17	100 / 100	219 ms	4416 KiB

sequence

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, K;
ll A[MAXN+10];

typedef __int128 dll;
struct Line { ll a, b, p; }; // ax+b
struct Frac
{
    ll u, d;
    Frac(ll _u, ll _d)
    {
        if(_d<0) u=-_u, d=-_d;
        else u=_u, d=_d;
    }
    bool operator < (const Frac &ot) const { return (dll)u*ot.d < (dll)ot.u*d; }
};
// If all queries are integer, change 'Frac' to 'div', be careful when different direction !!
ll div(ll u, ll d) { return u/d - ((u^d)<0 && u%d); }
struct CHT
{
    Frac cross(const Line &p, const Line &q) { return Frac(p.b-q.b, q.a-p.a); }
    deque<Line> V;
 
    // Lines are inserted from left to right
    // if p, q, r is lines in V, cross(p, q) < cross(q, r)
    // If not, reverse '<' in 'bool operator <'
    void update(Line p)
    {
        if(!V.empty() && V.back().a==p.a)
        {
            if(V.back().b<=p.b) return; // 'V.back()' is more optimal than 'p'
            V.pop_back();
        }
        while(V.size()>1 && !(cross(V[V.size()-2], V[V.size()-1]) < cross(V[V.size()-1], p))) V.pop_back();
        V.push_back(p);
    }
 
    int query(ll x)
    {
        assert(!V.empty());
        int lo=0, hi=V.size();
        while(lo+1<hi)
        {
            int mid=lo+hi>>1;
            if(cross(V[mid-1], V[mid]) < Frac(x, 1)) lo=mid;
            else hi=mid;
        }
        return V[lo].p;
    }
 
    // x must be queried from left to right ( same as push )
    int query2(ll x)
    {
        assert(!V.empty());
        while(V.size()>1 && cross(V[0], V[1]) < Frac(x, 1)) V.pop_front();
        return V[0].p;
    }
}cht;


namespace ailien
{
    ll dp[MAXN+10];
    int cnt[MAXN+10], memo[MAXN+10];
    // dp[i] := optimal dp value of i
    // cnt[i] := how much transitions were used in optimal dp[i]
    // memo[i] := previous transition position from i
    vector<int> V;

    void solve(ll lambda) // changes dp, cnt, memo, V
    {
        V.clear();
        // initialize dp, cnt, memo
        dp[0]=0;
        cht.V.clear();

	    cht.update({0, 0, 0});
        for(int i=1; i<=N; i++)
        {
            // get_opt(i), cost(p, q) must be implemented
            int opt = cht.query2(A[i]); // opt = argmin_{j<i} (dp[j] + cost(j, i)*2)
            dp[i]=dp[opt] + (A[i]-A[opt])*(A[i]-A[opt])*2 - lambda; // Don't forget *2
            cnt[i]=cnt[opt]+1;
            memo[i]=opt;
		    cht.update({-4*A[i], 2*A[i]*A[i]+dp[i], i});
        }
        // V = restore optimal solution
        for(int i=N; i>0;)
        {
            V.push_back(i);
            i=memo[i];
        }
        V.push_back(0);
        reverse(V.begin(), V.end());
    }

    void init(int _N)
    {
        N=_N;
    }

    // code for **minimum**
    pair<ll, vector<int>> ailien(int K)
    {
        ll lo=-1e18, hi=1e18; // range for lambda is [2*lo+1, 2*hi+1]
        while(lo+1<hi)
        {
            ll mid=lo+hi>>1;
            solve(2*mid+1);
            if(K<=cnt[N]) hi=mid;
            else lo=mid;
        }
        
        vector<int> L, R, ansV;
        solve(2*lo+1); L=V;
        solve(2*hi+1); R=V;

        if(L.size()-1==K) ansV=L;
        else if(R.size()-1==K) ansV=R;
        else
        {
            assert(L.size()-1<K && K<R.size()-1);
            for(int i=0; i+1<R.size(); i++)
            {
                int l=R[i], r=R[i+1];
                int lt=upper_bound(L.begin(), L.end(), l)-L.begin()-1;
    
                if(lt+1<L.size() && L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K)
                {
                    for(int j=0; j<=i; j++) ansV.push_back(R[j]);
                    for(int j=lt+1; j<L.size(); j++) ansV.push_back(L[j]);
                    assert(ansV.size()-1==K);
                    break;
                }
            }
        }

        solve(2*hi);
        ll ans=dp[N]/2+hi*K;
        return {ans, ansV};
    }
}


int main()
{
	scanf("%d%d", &N, &K); K++;
	for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
 
	for(int i=1; i<=N; i++) A[i]+=A[i-1];
    ailien::init(N);
    auto [ans, ansV] = ailien::ailien(K);
    ans=(A[N]*A[N]-ans)/2;
	printf("%lld\n", ans);
	for(int i=1; i+1<ansV.size(); i++) printf("%d ", ansV[i]);
	printf("\n");

}

Compilation message (stderr)

sequence.cpp: In member function 'int CHT::query(ll)':
sequence.cpp:52:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |             int mid=lo+hi>>1;
      |                     ~~^~~
sequence.cpp: In function 'std::pair<long long int, std::vector<int> > ailien::ailien(int)':
sequence.cpp:116:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |             ll mid=lo+hi>>1;
      |                    ~~^~~
sequence.cpp:126:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  126 |         if(L.size()-1==K) ansV=L;
      |            ~~~~~~~~~~^~~
sequence.cpp:127:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |         else if(R.size()-1==K) ansV=R;
      |                 ~~~~~~~~~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp:130:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  130 |             assert(L.size()-1<K && K<R.size()-1);
      |                    ~~~~~~~~~~^~
sequence.cpp:130:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             assert(L.size()-1<K && K<R.size()-1);
      |                                    ~^~~~~~~~~~~
sequence.cpp:131:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |             for(int i=0; i+1<R.size(); i++)
      |                          ~~~^~~~~~~~~
sequence.cpp:136:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |                 if(lt+1<L.size() && L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K)
      |                    ~~~~^~~~~~~~~
sequence.cpp:136:78: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |                 if(lt+1<L.size() && L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K)
      |                                                               ~~~~~~~~~~~~~~~^~~
sequence.cpp:139:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                     for(int j=lt+1; j<L.size(); j++) ansV.push_back(L[j]);
      |                                     ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp:140:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |                     assert(ansV.size()-1==K);
      |                            ~~~~~~~~~~~~~^~~
sequence.cpp: In function 'int main()':
sequence.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |  for(int i=1; i+1<ansV.size(); i++) printf("%d ", ansV[i]);
      |               ~~~^~~~~~~~~~~~
sequence.cpp:155:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |  scanf("%d%d", &N, &K); K++;
      |  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:156:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29