Submission #249424

#	Time	Username	Problem	Language	Result	Execution time	Memory
249424		mahmoudbadawy	Bigger segments (IZhO19_segments)	C++17	100 / 100	424 ms	105080 KiB

segments

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N=5e5+5;

int arr[N];
set<pair<int,int> > cur[N];
long long sum[N];
int n;

int get(long long s,int i)
{
	int st=i,en=n,ans=n+1;
	while(st<=en)
	{
		int mid=(st+en)/2;
		if(sum[mid]-sum[i]>=s)
		{
			ans=mid;
			en=mid-1;
		}
		else
			st=mid+1;
	}
	return ans;
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
		sum[i+1]=sum[i]+arr[i];
	}
	for(int i=1;i<n;i++)
	{
		int las=-1;
		cur[i].insert({1,1});
		while(cur[i].size())
		{
			auto x=*cur[i].rbegin();
			cur[i].erase(x);
			if(x.F==las)
				continue;
			cur[i+1].insert(x);
			int z=get(sum[i]-sum[x.S-1],i);
			cur[z].insert({x.F+1,i+1});
			if(las!=-1) break;
			las=x.F;
		}
	}
	if(!cur[n].size()) cur[n].insert({1,1});
	cout << (*cur[n].rbegin()).F << endl;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
segments.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27