Submission #712178

#	Time	Username	Problem	Language	Result	Execution time	Memory
712178		Pherokung	Bigger segments (IZhO19_segments)	C++14	100 / 100	366 ms	44188 KiB

segments

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
typedef pair<ll,ll> pa;
ll n,a,qs[500005],dp[500005],l,r,p,v;
set<pa> s;
set<pa> :: iterator it;
ll rang(int l,int r){
	return qs[r] - qs[l-1];
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a);
		qs[i] = qs[i-1]+a;
	}
	s.insert({0,0});
	
	for(int i=1;i<=n;i++){
		it = s.upper_bound({qs[i],1e18});
		--it;
		v = (*it).F, p = (*it).S;
		dp[i] = dp[p] + 1;
		it = s.lower_bound({qs[i] + rang(p+1,i),-1e18});
		
		s.erase(it,s.end());
		s.insert({qs[i] + rang(p+1,i),i});
	}
	
	printf("%lld",dp[n]);
}

Compilation message (stderr)

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

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