Submission #221147

#	Time	Username	Problem	Language	Result	Execution time	Memory
221147		cgiosy	Split the sequence (APIO14_sequence)	C++17	78 / 100	1118 ms	3200 KiB

sequence

#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==-1) {
			x=0;
			for(int i=1; i<K+2; i++) x+=ll(A[Q[i]]-A[Q[i-1]])*A[Q[i-1]];
		}
		cout<<x<<'\n';
		for(int i=1; i<K+1; i++) cout<<Q[i]<<' ';
		exit(0);
	};
	auto ga=[&](int k, ll x) {
		vector<int> Q(k+1);
		for(int i=N, j=k; i; 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[lk,lx]=f(2*r-1);
	auto L=ga(lk, lx/2);
	auto[rk,rx]=f(2*r+1);
	auto R=ga(rk, rx/2);

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

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:13: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:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In lambda function:
sequence.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In function 'int main()':
sequence.cpp:70:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll m=l+r>>1;
        ~^~
sequence.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1, p=0; i<R.size(); i++) {
                    ~^~~~~~~~~
sequence.cpp:86:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(L[p]>=R[i] && i+L.size()-p==K+2) {
                    ~~~~~~~~~~~~^~~~~
sequence.cpp:87:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(p<L.size()) M[i++]=L[p++];
          ~^~~~~~~~~

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