Submission #210246

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
210246	2020-03-17T00:24:00 Z	super_j6	Bigger segments (IZhO19_segments)	C++14	0 / 100	5 ms	380 KB

segments

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define endl '\n'
#define pi pair<long long, int>
#define f first
#define s second
 
const int maxn = 500001;
int n;
long long 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((*s.begin()).f < p.f) s.erase(s.begin());
		s.insert(p);
	}
	
	cout << dp[n] << endl;
 
	return 0;
}

Subtask #1

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 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	Correct	4 ms	376 KB	Output is correct
9	Correct	5 ms	380 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Incorrect	5 ms	376 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 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	Correct	4 ms	376 KB	Output is correct
9	Correct	5 ms	380 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Incorrect	5 ms	376 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 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	Correct	4 ms	376 KB	Output is correct
9	Correct	5 ms	380 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Incorrect	5 ms	376 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 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	Correct	4 ms	376 KB	Output is correct
9	Correct	5 ms	380 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Incorrect	5 ms	376 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 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	Correct	4 ms	376 KB	Output is correct
9	Correct	5 ms	380 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Incorrect	5 ms	376 KB	Output isn't correct
13	Halted	0 ms	0 KB	-