Submission #221131

#	Time	Username	Problem	Language	Result	Execution time	Memory
221131		cgiosy	Split the sequence (APIO14_sequence)	C++17	61 / 100	1117 ms	3448 KiB

sequence

#pragma GCC optimize("O3,fast-math")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, K;
	cin>>N>>K;
	vector<int> A(N+1), 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 ll(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])*m;
		};
		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 x=-1) {
		if(~x) {
			int p=x=0;
			for(int i:Q) x+=ll(A[i]-A[p])*A[p], p=i;
			x+=ll(A[N]-A[p])*A[p];
		}
		cout<<x<<'\n';
		for(int i:Q) cout<<i<<' ';
		exit(0);
	};
	auto ga=[&](int k, ll x) {
		vector<int> Q(k-1);
		for(int i=N, j=k-1; i=P[i];) Q[--j]=i;
		if(k==K+1) go(Q, x);
		return Q;
	};

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

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

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

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:14: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:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In lambda function:
sequence.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In lambda function:
sequence.cpp:65:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   for(int i=N, j=k-1; i=P[i];) Q[--j]=i;
sequence.cpp: In function 'int main()':
sequence.cpp:72:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll m=l+r>>1;
        ~^~

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