CSES - Datatähti 2020 loppu - Results
Submission details
Task:Riippuliito
Sender:Juho Röyskö
Submission time:2020-02-09 14:04:30 +0200
Language:C++11
Status:READY
Result:39
Feedback
groupverdictscore
#1ACCEPTED18
#2ACCEPTED21
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s2, 3details
#9ACCEPTED0.04 s2, 3details
#10ACCEPTED0.03 s2, 3details
#11ACCEPTED0.01 s2, 3details
#12ACCEPTED0.01 s2, 3details
#13ACCEPTED0.02 s2, 3details
#14ACCEPTED0.04 s2, 3details
#15ACCEPTED0.02 s3details
#16--3details
#17--3details
#18ACCEPTED0.03 s3details
#19ACCEPTED0.05 s3details
#20--3details
#21--3details
#22ACCEPTED0.01 s1, 2, 3details
#23ACCEPTED0.01 s1, 2, 3details
#24ACCEPTED0.01 s1, 2, 3details
#25ACCEPTED0.01 s1, 2, 3details
#26ACCEPTED0.01 s1, 2, 3details
#27ACCEPTED0.01 s1, 2, 3details
#28ACCEPTED0.01 s1, 2, 3details
#29ACCEPTED0.01 s1, 2, 3details

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int m[202020];
vector<int> v;
int r;

void search(int a, int b, int x, int l) {
	int mx = 0;
	vector<int> v2;
	for (int i = a; i <= b; ++i) {
		if (v[i] > mx) {
			mx = v[i];
			v2.clear();
		}
		if (v[i] == mx) v2.push_back(i);
	}
	int n = v2.size();
	if (n == 0) {
		r = max(r, l);
		return;
	}
	search(v2[n-1] + 1, b, mx, l + 1);

	for (int i = n-1; i >= 0; --i) {
		if (i == 0) search(a, v2[i]-1, mx, l+1);
		else search(v2[i-1] + 1, v2[i] - 1, mx, l+1);
	}
	r = max(r, l);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) {
		int h;
		cin >> h;

		v.push_back(h);
	}
	search(0, n-1, 2e9, 0);

	cout << r << '\n';
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
1 2 3 4 5 6 7 8 9 10

correct output
10

user output
10

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
10 9 8 7 6 5 4 3 2 1

correct output
10

user output
10

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
10 9 6 10 10 3 6 7 6 5

correct output
4

user output
4

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
51 90 27 98 85 47 14 55 82 52

correct output
6

user output
6

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
9 65 90 86 45 52 52 95 40 85

correct output
5

user output
5

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
10
3 46 77 16 59 32 22 41 87 89

correct output
7

user output
7

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1

user output
1

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
5000

user output
5000

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
5000
5000 4999 4998 4997 4996 4995 ...

correct output
5000

user output
5000

Test 11

Group: 2, 3

Verdict: ACCEPTED

input
5000
10 8 10 5 4 9 2 9 10 10 1 2 7 ...

correct output
9

user output
9

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
5000
655923386 310000737 281882248 ...

correct output
28

user output
28

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
5000
123456789 123456790 123456791 ...

correct output
2706

user output
2706

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
5000
123456789 123456790 123456791 ...

correct output
5000

user output
5000

Test 15

Group: 3

Verdict: ACCEPTED

input
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1

user output
1

Test 16

Group: 3

Verdict:

input
200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
200000

user output
(empty)

Test 17

Group: 3

Verdict:

input
200000
200000 199999 199998 199997 19...

correct output
200000

user output
(empty)

Test 18

Group: 3

Verdict: ACCEPTED

input
200000
4 7 8 3 3 10 3 4 2 6 10 8 5 8 ...

correct output
10

user output
10

Test 19

Group: 3

Verdict: ACCEPTED

input
200000
824527039 112439661 517794857 ...

correct output
43

user output
43

Test 20

Group: 3

Verdict:

input
200000
123456789 123456790 123456791 ...

correct output
30764

user output
(empty)

Test 21

Group: 3

Verdict:

input
200000
123456789 123456790 123456791 ...

correct output
61367

user output
(empty)

Test 22

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
1

correct output
1

user output
1

Test 23

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
1 1

correct output
1

user output
1

Test 24

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
1 2

correct output
2

user output
2

Test 25

Group: 1, 2, 3

Verdict: ACCEPTED

input
2
2 1

correct output
2

user output
2

Test 26

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
1 2 1

correct output
2

user output
2

Test 27

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
1 2 3

correct output
3

user output
3

Test 28

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
3 2 1

correct output
3

user output
3

Test 29

Group: 1, 2, 3

Verdict: ACCEPTED

input
3
2 1 2

correct output
2

user output
2