Submission #367575

#	Time	Username	Problem	Language	Result	Execution time	Memory
367575		arnold518	Split the sequence (APIO14_sequence)	C++14	100 / 100	257 ms	6752 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];

struct Line
{
	ll a, b; int p;
};

long double cross(Line p, Line q) { return (long double)(p.b-q.b)/(q.a-p.a); }

struct CHT
{
	int pos=0;
	vector<Line> S;
	void init()
	{
		S.clear();
		pos=0;
	}
	void update(Line p)
	{
		if(!S.empty() && S.back().a==p.a)
		{
			if(S.back().b<=p.b) return;
			S.pop_back();
		}
		while(S.size()>1 && cross(S[S.size()-2], S[S.size()-1])>=cross(S[S.size()-1], p)) S.pop_back();
		S.push_back(p);
	}
	int query(ll x)
	{
		if(pos>=S.size()) pos=S.size()-1;
		else while(pos+1<S.size() && cross(S[pos], S[pos+1])<=x) pos++;
		return S[pos].p;
	}
}cht;

pll dp[MAXN+10];
int memo[MAXN+10];
vector<int> V, ansV;
void solve(ll lambda)
{
	cht.init();
	V.clear();
	cht.update({0, 0, 0});
	for(int i=0; i<=N; i++) dp[i]={0, 0};
	for(int i=1; i<=N; i++)
	{
		int t=cht.query(A[i]);
		dp[i].first=dp[t].first+(A[i]-A[t])*(A[i]-A[t])*2+lambda;
		dp[i].second=dp[t].second+1;
		memo[i]=t;
		cht.update({-4*A[i], 2*A[i]*A[i]+dp[i].first, i});
	}
	for(int i=N; i>0;)
	{
		V.push_back(i);
		i=memo[i];
	}
	V.push_back(0);
	reverse(V.begin(), V.end());	
}

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];

	ll lo=-1, hi=1e18;
	while(lo+1<hi)
	{
		ll mid=lo+hi>>1;
		solve(2*mid+1);
		if(dp[N].second<K) hi=mid;
		else lo=mid;
	}

	vector<int> L, R;
	solve(2*hi+1); L=V;
	solve(2*lo+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].first/2-hi*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:41:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   if(pos>=S.size()) pos=S.size()-1;
      |      ~~~^~~~~~~~~~
sequence.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   else while(pos+1<S.size() && cross(S[pos], S[pos+1])<=x) pos++;
      |              ~~~~~^~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:83:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |   ll mid=lo+hi>>1;
      |          ~~^~~
sequence.cpp:93:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |  if(L.size()-1==K)
      |     ~~~~~~~~~~^~~
sequence.cpp:97:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |  else if(R.size()-1==K)
      |          ~~~~~~~~~~^~~
sequence.cpp:104:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i=0; i+1<R.size(); i++)
      |                ~~~^~~~~~~~~
sequence.cpp:109:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |    if(lt+1<L.size() && L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K)
      |       ~~~~^~~~~~~~~
sequence.cpp:109:65: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |    if(lt+1<L.size() && L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K)
      |                                                  ~~~~~~~~~~~~~~~^~~
sequence.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int j=lt+1; j<L.size(); j++) ansV.push_back(L[j]);
      |                     ~^~~~~~~~~
sequence.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for(int i=1; i+1<ansV.size(); i++) printf("%d ", ansV[i]);
      |               ~~~^~~~~~~~~~~~
sequence.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |  scanf("%d%d", &N, &K); K++;
      |  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:76:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |  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