Submission #290837

#	Time	Username	Problem	Language	Result	Execution time	Memory
290837		Plurm	Bigger segments (IZhO19_segments)	C++11	100 / 100	346 ms	41468 KiB

segments

#include <bits/stdc++.h>
using namespace std;
long long qs[500005];
int dp[500005];
long long val[500005];
map<long long, int> s;
int main(){
	int n;
	scanf("%d",&n);
	s[0ll] = 0;
	for(int i = 1; i <= n; i++){
		int x;
		scanf("%d",&x);
		qs[i] = qs[i-1] + x;
		int j = (--s.upper_bound(qs[i]))->second;
		dp[i] = dp[j]+1;
		val[i] = qs[i]-qs[j];
		while(!s.empty() && s.rbegin()->first >= 2ll*qs[i]-qs[j]) s.erase(s.rbegin()->first);
		s[2ll*qs[i]-qs[j]] = i;
	}
	printf("%d\n",dp[n]);
	return 0;
}

Compilation message (stderr)

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

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