Submission #221256

#	Time	Username	Problem	Language	Result	Execution time	Memory
221256		cgiosy	Split the sequence (APIO14_sequence)	C++17	100 / 100	784 ms	3500 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ld=double;
using ll=long long;

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, K;
	cin>>N>>K; ++K;
	vector<ll> A(N+1);
	vector<int> P(N+1);
	for(int i=1; i<=N; i++) cin>>A[i], A[i]+=A[i-1];

	auto f=[&](ll dt) {
		vector<int> C(N+1), X(1<<32-__builtin_clz(N));
		vector<ll> D(N+1);
		auto f=[&](int i, int x) {
			return (A[x]-A[i])*A[i]*2 + D[i];
		};
		auto cmp=[&](int i, int j, int x) {
			// return f(i, x)-C[i]*dt>f(j, x)-C[j]*dt;
			return f(i, x)-f(j, x)>(C[i]-C[j])*dt;
		};
		auto add=[&](int b) {
			int s=1, e=N, i=1;
			while(s<=e) {
				int&a=X[i];
				if(cmp(b, a, s)) swap(a, b);
				if(cmp(a, b, e)) break;
				int m=s+e>>1;
				if(cmp(b, a, m)) swap(a, b), e=m-1, i=i*2;
				else s=m+1, i=i*2+1;
			}
		};
		auto get=[&](int x) {
			int s=1, e=N, i=1, k=0;
			while(s<=e) {
				if(cmp(X[i], k, x)) k=X[i];
				int m=s+e>>1;
				if(x<=m) e=m-1, i=i*2;
				else s=m+1, i=i*2+1;
			}
			return k;
		};
		for(int i=1; i<=N; i++) {
			int k=get(i);
			P[i]=k;
			C[i]=C[k]+1;
			D[i]=f(k, i);
			add(i);
		}
		return make_pair(C[N], D[N]);
	};
	/*
	auto go=[&](const vector<int>& Q) {
		ll pm=0;
		for(int i=1; i<=Q[1]; i++)
			pm=max(pm, A[i]-A[i-1]);
		for(int i=2; i<Q.size(); i++) {
			ll m=0;
			for(int j=Q[i-1]+1; j<=Q[i]; j++)
				m=max(m, A[j]-A[j-1]);
			if(abs(A[Q[i]]+A[Q[i-2]]-2*A[Q[i-1]]) > max(pm, m)) {
				cout<<"No\n";
				exit(0);
			}
			pm=m;
		}
		cout<<"Yes\n";
		for(int i=1; i<K; i++) cout<<Q[i]<<' ';
		exit(0);
	};
	*/
	auto go=[&](const vector<int>& Q) {
		ll x=0;
		for(int i=1; i<K+1; i++) x+=ll(A[Q[i]]-A[Q[i-1]])*A[Q[i-1]];
		cout<<x<<'\n';
		for(int i=1; i<K; i++) cout<<Q[i]<<' ';
		exit(0);
	};
	auto ga=[&](int k) {
		vector<int> Q(k+1);
		for(int i=N, j=k; i; i=P[i]) Q[j--]=i;
		if(k==K) go(Q);
		return Q;
	};

	ll l=0, r=1e17;
	while(l<r) {
		ll m=l+(r-l>>1);
		auto[k,x]=f(m*2+1);
		if(k>K) l=m+1;
		else if(k<K) r=m;
		else ga(k);
	}

	auto[lk,lx]=f(l+r-1);
	auto L=ga(lk);
	auto[rk,rx]=f(l+r+1);
	auto R=ga(rk);

	vector<int> M(K+1);
	for(int i=1, p=0; i<L.size(); i++) {
		M[i-1]=L[i-1];
		while(R[p]<=L[i-1]) p++;
		if(R[p]>=L[i] && i+R.size()-p==K+1) {
			while(p<R.size()) M[i++]=R[p++];
			go(M);
			break;
		}
	}

	cout<<"No\n";
}

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:15:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   vector<int> C(N+1), X(1<<32-__builtin_clz(N));
                            ~~^~~~~~~~~~~~~~~~~
sequence.cpp: In lambda function:
sequence.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In lambda function:
sequence.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In function 'int main()':
sequence.cpp:90:12: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   ll m=l+(r-l>>1);
           ~^~
sequence.cpp:91:11: warning: unused variable 'x' [-Wunused-variable]
   auto[k,x]=f(m*2+1);
           ^
sequence.cpp:103:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1, p=0; i<L.size(); i++) {
                    ~^~~~~~~~~
sequence.cpp:106:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(R[p]>=L[i] && i+R.size()-p==K+1) {
                    ~~~~~~~~~~~~^~~~~
sequence.cpp:107:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(p<R.size()) M[i++]=R[p++];
          ~^~~~~~~~~
sequence.cpp:97:12: warning: unused variable 'lx' [-Wunused-variable]
  auto[lk,lx]=f(l+r-1);
            ^
sequence.cpp:99:12: warning: unused variable 'rx' [-Wunused-variable]
  auto[rk,rx]=f(l+r+1);
            ^

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