CSES - DatatÃ¤hti 2020 loppu - Results
 Task: Riippuliito Sender: Into Almiala Submission time: 2020-02-09 15:04:25 +0200 Language: C++11 Status: READY Result: 0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.01 s1, 2, 3details
#30.01 s1, 2, 3details
#40.01 s1, 2, 3details
#50.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#70.01 s1, 2, 3details
#80.01 s2, 3details
#90.01 s2, 3details
#100.01 s2, 3details
#110.01 s2, 3details
#120.01 s2, 3details
#130.01 s2, 3details
#140.01 s2, 3details
#150.04 s3details
#160.07 s3details
#170.07 s3details
#180.05 s3details
#190.10 s3details
#200.10 s3details
#210.10 s3details
#22ACCEPTED0.01 s1, 2, 3details
#230.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
#290.01 s1, 2, 3details

### Code

#include <iostream>

using namespace std;

int n, N;
int t[1<<19];

void upd(int x, int k) {
x += N;
t[x] = k;
for (x /= 2; x > 0; x /= 2) {
t[x] = max(t[2*x], t[2*x+1]);
}
}

pair<int,int> max_range(int a, int b) {
a += N;
b += N;
int m = 0;
int i = 0;
while (a <= b) {
if (b%2 == 0) {
m = max(m, t[b--]);
i = b+1;
}
if (a%2 == 1) {
m = max(m, t[a++]);
i = a-1;
}
a /= 2;
b /= 2;
}
while (i < N) {
i *= 2;
if (t[i+1] == m) i++;
}
return {m, i-N};
}

int search(int a, int b) {
if (b < a) return 0;
if (a == b) return 1;
pair<int,int> m = max_range(a, b);
int x = m.second;
return max(search(a, x-1), search(x+1, b))+1;
}

int main() {
cin >> n;
N = n;
while (__builtin_popcount(N) > 1) N^=N&-N;
N <<= 1;
for (int i = 0; i < n; i++) {
int h;
cin >> h;
upd(i, h);
}
cout << search(0, n-1) << endl;
}

### Test details

#### Test 1

Group: 1, 2, 3

Verdict:

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

correct output
1

user output
4

#### Test 2

Group: 1, 2, 3

Verdict:

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

correct output
10

user output
6

#### Test 3

Group: 1, 2, 3

Verdict:

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

correct output
10

user output
5

#### Test 4

Group: 1, 2, 3

Verdict:

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

correct output
4

user output
5

#### Test 5

Group: 1, 2, 3

Verdict:

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

correct output
6

user output
5

#### 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:

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

correct output
7

user output
6

#### Test 8

Group: 2, 3

Verdict:

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

correct output
1

user output
13

#### Test 9

Group: 2, 3

Verdict:

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

correct output
5000

user output
23

#### Test 10

Group: 2, 3

Verdict:

input
5000
5000 4999 4998 4997 4996 4995 ...

correct output
5000

user output
17

#### Test 11

Group: 2, 3

Verdict:

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

correct output
9

user output
19

#### Test 12

Group: 2, 3

Verdict:

input
5000
655923386 310000737 281882248 ...

correct output
28

user output
21

#### Test 13

Group: 2, 3

Verdict:

input
5000
123456789 123456790 123456791 ...

correct output
2706

user output
22

#### Test 14

Group: 2, 3

Verdict:

input
5000
123456789 123456790 123456791 ...

correct output
5000

user output
23

#### Test 15

Group: 3

Verdict:

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

correct output
1

user output
18

#### 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
34

#### Test 17

Group: 3

Verdict:

input
200000
200000 199999 199998 199997 19...

correct output
200000

user output
23

#### Test 18

Group: 3

Verdict:

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

correct output
10

user output
24

#### Test 19

Group: 3

Verdict:

input
200000
824527039 112439661 517794857 ...

correct output
43

user output
31

#### Test 20

Group: 3

Verdict:

input
200000
123456789 123456790 123456791 ...

correct output
30764

user output
32

#### Test 21

Group: 3

Verdict:

input
200000
123456789 123456790 123456791 ...

correct output
61367

user output
31

#### Test 22

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
1

correct output
1

user output
1

Group: 1, 2, 3

Verdict:

input
2
1 1

correct output
1

user output
2

#### 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

Group: 1, 2, 3

Verdict:

input
3
2 1 2

correct output
2

user output
3