Submission #210234

#	Time	Username	Problem	Language	Result	Execution time	Memory
210234		super_j6	Bigger segments (IZhO19_segments)	C++14	0 / 100	5 ms	376 KiB

segments

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define endl '\n'
#define pi pair<long long, long long>
#define f first
#define s second
 
const int maxn = 500001;
int n;
int a[maxn], dp[maxn];
set<pi> s;
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	s.insert({0, 0});
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] = -a[i] + a[i - 1];
		
		pi p = *s.lower_bound({a[i], 0});
		
		dp[i] = dp[p.s] + 1;
		p = {2 * a[i] - a[p.s], i};
		
		while((*prev(s.end())).f < p.f) s.erase(prev(s.end()));
		
		s.insert(p);
	}
	
	cout << dp[(*s.begin()).s] << endl;
 
	return 0;
}

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