oj.uz

Submission #210234

# Submission time Handle Problem Language Result Execution time Memory
210234 2020-03-17T00:14:00 Z super_j6 Bigger segments (IZhO19_segments) C++14
0 / 100
 5 ms 376 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Incorrect 5 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -