oj.uz

Submission #92672

# Submission time Handle Problem Language Result Execution time Memory
92672 2019-01-04T09:52:24 Z toloraia Money (IZhO17_money) C++14
100 / 100
 1406 ms 215824 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6;

int n;
int a[MAXN + 5];
int b[MAXN + 5];
int A[MAXN + 5][25], B[MAXN + 5][25];
int le[MAXN + 5];
int dp[MAXN + 5];
int BI[MAXN + 5];

int datvla (int l, int r){
    if (l > r)
        return n + 1;
    int x = BI[r - l + 1];
    return min (A[l][x], B[r][x]);
}

int main()
{
    BI[2] = 1;
    for (int i = 3; i <= MAXN; i++){
        BI[i] = BI[i - 1];
        if ((i & (i - 1)) == 0)
            BI[i]++;
    }
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    for (int i = 1; i <= MAXN; i++)
        b[i] = n + 1;
    for (int i = n; i >= 1; i--)
        b[a[i]] = i;
    for (int i = 1; i <= MAXN; i++){
        A[i][0] = b[i];
        B[i][0] = b[i];
    }
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= MAXN; j++){
            A[j][i] = A[j][i - 1];
            if (j + (1<<(i - 1)) <= MAXN)
                A[j][i] = min (A[j][i], A[j + (1<<(i - 1))][i - 1]);
            B[j][i] = B[j][i - 1];
            if (j - (1<<(i - 1)) >= 1)
                B[j][i] = min (B[j][i], B[j - (1<<(i - 1))][i - 1]);
        }
    le[1] = 1;
    for (int i = 2; i <= n; i++){
        le[i] = i;
        if (a[i] >= a[i - 1])
            le[i] = le[i - 1];
    }
    dp[1] = 1;
    for (int i = 2; i <= n; i++){
        int I = i;
        for (int j = 19; j >= 0; j--){
            if (I - (1<<j) < le[i])
                continue;
            if (datvla (a[I - (1<<j)] + 1, a[i] - 1) >= I - (1<<j))
                I -= (1<<j);
        }
        dp[i] = dp[I - 1] + 1;
    }
    cout<<dp[n]<<endl;
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 203896 KB Output is correct
2 Correct 703 ms 203896 KB Output is correct
3 Correct 721 ms 204000 KB Output is correct
4 Correct 696 ms 203896 KB Output is correct
5 Correct 718 ms 204024 KB Output is correct
6 Correct 737 ms 203996 KB Output is correct
7 Correct 672 ms 203896 KB Output is correct
8 Correct 675 ms 203868 KB Output is correct
9 Correct 696 ms 203892 KB Output is correct
10 Correct 664 ms 203896 KB Output is correct
11 Correct 662 ms 204024 KB Output is correct
12 Correct 738 ms 203924 KB Output is correct
13 Correct 721 ms 204060 KB Output is correct
14 Correct 788 ms 203896 KB Output is correct
15 Correct 780 ms 203824 KB Output is correct
16 Correct 796 ms 203900 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 203896 KB Output is correct
2 Correct 703 ms 203896 KB Output is correct
3 Correct 721 ms 204000 KB Output is correct
4 Correct 696 ms 203896 KB Output is correct
5 Correct 718 ms 204024 KB Output is correct
6 Correct 737 ms 203996 KB Output is correct
7 Correct 672 ms 203896 KB Output is correct
8 Correct 675 ms 203868 KB Output is correct
9 Correct 696 ms 203892 KB Output is correct
10 Correct 664 ms 203896 KB Output is correct
11 Correct 662 ms 204024 KB Output is correct
12 Correct 738 ms 203924 KB Output is correct
13 Correct 721 ms 204060 KB Output is correct
14 Correct 788 ms 203896 KB Output is correct
15 Correct 780 ms 203824 KB Output is correct
16 Correct 796 ms 203900 KB Output is correct
17 Correct 786 ms 203896 KB Output is correct
18 Correct 781 ms 204024 KB Output is correct
19 Correct 783 ms 203896 KB Output is correct
20 Correct 793 ms 203896 KB Output is correct
21 Correct 799 ms 203896 KB Output is correct
22 Correct 780 ms 203984 KB Output is correct
23 Correct 749 ms 203896 KB Output is correct
24 Correct 800 ms 203896 KB Output is correct
25 Correct 797 ms 203896 KB Output is correct
26 Correct 663 ms 203892 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 203896 KB Output is correct
2 Correct 703 ms 203896 KB Output is correct
3 Correct 721 ms 204000 KB Output is correct
4 Correct 696 ms 203896 KB Output is correct
5 Correct 718 ms 204024 KB Output is correct
6 Correct 737 ms 203996 KB Output is correct
7 Correct 672 ms 203896 KB Output is correct
8 Correct 675 ms 203868 KB Output is correct
9 Correct 696 ms 203892 KB Output is correct
10 Correct 664 ms 203896 KB Output is correct
11 Correct 662 ms 204024 KB Output is correct
12 Correct 738 ms 203924 KB Output is correct
13 Correct 721 ms 204060 KB Output is correct
14 Correct 788 ms 203896 KB Output is correct
15 Correct 780 ms 203824 KB Output is correct
16 Correct 796 ms 203900 KB Output is correct
17 Correct 786 ms 203896 KB Output is correct
18 Correct 781 ms 204024 KB Output is correct
19 Correct 783 ms 203896 KB Output is correct
20 Correct 793 ms 203896 KB Output is correct
21 Correct 799 ms 203896 KB Output is correct
22 Correct 780 ms 203984 KB Output is correct
23 Correct 749 ms 203896 KB Output is correct
24 Correct 800 ms 203896 KB Output is correct
25 Correct 797 ms 203896 KB Output is correct
26 Correct 663 ms 203892 KB Output is correct
27 Correct 798 ms 203892 KB Output is correct
28 Correct 818 ms 203896 KB Output is correct
29 Correct 799 ms 203896 KB Output is correct
30 Correct 804 ms 203900 KB Output is correct
31 Correct 808 ms 203900 KB Output is correct
32 Correct 810 ms 203888 KB Output is correct
33 Correct 816 ms 203888 KB Output is correct
34 Correct 810 ms 203892 KB Output is correct
35 Correct 776 ms 203896 KB Output is correct
36 Correct 782 ms 203912 KB Output is correct
37 Correct 779 ms 203896 KB Output is correct
38 Correct 774 ms 203896 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 203896 KB Output is correct
2 Correct 703 ms 203896 KB Output is correct
3 Correct 721 ms 204000 KB Output is correct
4 Correct 696 ms 203896 KB Output is correct
5 Correct 718 ms 204024 KB Output is correct
6 Correct 737 ms 203996 KB Output is correct
7 Correct 672 ms 203896 KB Output is correct
8 Correct 675 ms 203868 KB Output is correct
9 Correct 696 ms 203892 KB Output is correct
10 Correct 664 ms 203896 KB Output is correct
11 Correct 662 ms 204024 KB Output is correct
12 Correct 738 ms 203924 KB Output is correct
13 Correct 721 ms 204060 KB Output is correct
14 Correct 788 ms 203896 KB Output is correct
15 Correct 780 ms 203824 KB Output is correct
16 Correct 796 ms 203900 KB Output is correct
17 Correct 786 ms 203896 KB Output is correct
18 Correct 781 ms 204024 KB Output is correct
19 Correct 783 ms 203896 KB Output is correct
20 Correct 793 ms 203896 KB Output is correct
21 Correct 799 ms 203896 KB Output is correct
22 Correct 780 ms 203984 KB Output is correct
23 Correct 749 ms 203896 KB Output is correct
24 Correct 800 ms 203896 KB Output is correct
25 Correct 797 ms 203896 KB Output is correct
26 Correct 663 ms 203892 KB Output is correct
27 Correct 798 ms 203892 KB Output is correct
28 Correct 818 ms 203896 KB Output is correct
29 Correct 799 ms 203896 KB Output is correct
30 Correct 804 ms 203900 KB Output is correct
31 Correct 808 ms 203900 KB Output is correct
32 Correct 810 ms 203888 KB Output is correct
33 Correct 816 ms 203888 KB Output is correct
34 Correct 810 ms 203892 KB Output is correct
35 Correct 776 ms 203896 KB Output is correct
36 Correct 782 ms 203912 KB Output is correct
37 Correct 779 ms 203896 KB Output is correct
38 Correct 774 ms 203896 KB Output is correct
39 Correct 963 ms 209484 KB Output is correct
40 Correct 1060 ms 213240 KB Output is correct
41 Correct 917 ms 208376 KB Output is correct
42 Correct 879 ms 207868 KB Output is correct
43 Correct 861 ms 206712 KB Output is correct
44 Correct 1032 ms 215672 KB Output is correct
45 Correct 1014 ms 215824 KB Output is correct
46 Correct 1014 ms 215644 KB Output is correct
47 Correct 1105 ms 215624 KB Output is correct
48 Correct 1004 ms 215660 KB Output is correct
49 Correct 1137 ms 215572 KB Output is correct
50 Correct 1185 ms 215712 KB Output is correct
51 Correct 1233 ms 215540 KB Output is correct
52 Correct 1135 ms 215796 KB Output is correct
53 Correct 1224 ms 215716 KB Output is correct
54 Correct 1238 ms 215672 KB Output is correct
55 Correct 1242 ms 215624 KB Output is correct
56 Correct 1161 ms 215672 KB Output is correct
57 Correct 1149 ms 215604 KB Output is correct
58 Correct 1188 ms 215736 KB Output is correct
59 Correct 1208 ms 215532 KB Output is correct
60 Correct 1285 ms 215556 KB Output is correct
61 Correct 1406 ms 215528 KB Output is correct
62 Correct 1394 ms 215732 KB Output is correct