oj.uz

답안 #471914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
471914 2021-09-11T16:58:14 Z qwerasdfzxcl 밀림 점프 (APIO21_jumps) C++14
33 / 100
 4000 ms 170048 KB 
#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> sp1[200200], sp2[200200], sp3[200200], sp4[200200], a;
int n, l[200200], r[200200], INV[200200];
struct MST{
    vector<int> tree[400400];
    int sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i].push_back(a[i-sz]);
        for (int i=sz-1;i;i--){
            tree[i].resize(tree[i<<1].size()+tree[i<<1|1].size());
            merge(tree[i<<1].begin(), tree[i<<1].end(), tree[i<<1|1].begin(), tree[i<<1|1].end(), tree[i].begin());
        }
    }
    int query(int l, int r, int x){
        int ret = -1;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                auto iter = lower_bound(tree[l].begin(), tree[l].end(), x);
                if (iter!=tree[l].begin()) ret = max(ret, *(--iter));
                l++;
            }
            if (r&1){
                --r;
                auto iter = lower_bound(tree[r].begin(), tree[r].end(), x);
                if (iter!=tree[r].begin()) ret = max(ret, *(--iter));
            }
        }
        return ret;
    }
    int query2(int l, int r){
        int ret = -1;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                ret = max(ret, tree[l].back());
                l++;
            }
            if (r&1){
                --r;
                ret = max(ret, tree[r].back());
            }
        }
        return ret;
    }
}tree;

int geth(int x){
    if (x<0) return -1e9;
    if (x>=n) return -1e9;
    return a[x];
}

void init(int N, std::vector<int> H) {
    n = N, a = H;
    for (int i=0;i<n;i++){
        INV[H[i]] = i;
        sp1[i].push_back(H[i]);
        sp2[i].push_back(H[i]);
    }
    for (int j=1;j<20;j++){
        for (int i=0;i<n;i++){
            if (i-(1<<j)+1<0) sp1[i].push_back(-1);
            else sp1[i].push_back(max(sp1[i][j-1], sp1[i-(1<<(j-1))][j-1]));
            if (i+(1<<j)-1>=n) sp2[i].push_back(-1);
            else sp2[i].push_back(max(sp2[i][j-1], sp2[i+(1<<(j-1))][j-1]));
        }
    }
    for (int i=0;i<n;i++){
        int cur = i-1, cur2 = -1e9;
        for (int j=19;j>=0;j--) if (cur!=-1 && sp1[cur][j]!=-1 && max(cur2, sp1[cur][j])<H[i]){
            cur2 = max(cur2, sp1[cur][j]);
            cur -= (1<<j);
        }
        l[i] = cur; cur = i+1, cur2 = -1e9;
        for (int j=19;j>=0;j--) if (cur!=n && sp2[cur][j]!=-1 && sp2[cur][j]<H[i]){
            cur2 = max(cur2, sp1[cur][j]);
            cur += (1<<j);
        }
        r[i] = cur;
        if (geth(l[i])>=geth(r[i])) sp3[i].push_back(l[i]);
        else sp3[i].push_back(r[i]);
        sp4[i].push_back(r[i]);
        //printf("%d %d\n", l[i], r[i]);
    }
    for (int j=1;j<20;j++){
        for (int i=0;i<n;i++){
            if (sp3[i][j-1]==-1) sp3[i].push_back(-1);
            else sp3[i].push_back(sp3[sp3[i][j-1]][j-1]);
            if (sp4[i][j-1]==n) sp4[i].push_back(n);
            else sp4[i].push_back(sp4[sp4[i][j-1]][j-1]);
        }
    }
    tree.init(n);
}

int minimum_jumps(int A, int B, int C, int D) {
    int mx = tree.query2(C, D+1);
    int cur2 = B, cur3 = -1;
    for (int j=19;j>=0;j--) if (cur2-(1<<j)+1>=A && max(sp1[cur2][j], cur3)<mx){
        cur3 = max(sp1[cur2][j], cur3);
        cur2 -= (1<<j);
    }
    A = cur2+1;
    int tmp = tree.query(A, B+1, mx);
    if (tmp==-1) return -1;

    int cur = INV[tmp], ans = 0;
    /*cur2 = C, cur3 = -1;
    for (int j=19;j>=0;j--) if (cur2+(1<<j)-1<=D && max(sp2[cur2][j], cur3)<a[cur]){
        cur3 = max(sp2[cur2][j], cur3);
        cur2 += (1<<j);
    }
    C = cur2;*/

    /*for (int j=19;j>=0;j--) if (sp3[cur][j]!=-1 && a[sp3[cur][j]]<mx && sp3[cur][j]<C) cur = sp3[cur][j], ans += (1<<j);
    for (int j=19;j>=0;j--) if (sp4[cur][j]!=n && a[sp4[cur][j]]<mx && sp4[cur][j]<C) cur = sp4[cur][j], ans += (1<<j);
    if (cur==-1 || cur==n) return -1;
    cur = sp4[cur][0], ans++;
    if (cur<C || cur>D) return -1;*/

    int ret = 1e9, tmp3 = 0;
    while(cur!=-1 && a[cur]<=mx){
        cur2 = cur, ans = tmp3;
        for (int j=19;j>=0;j--) if (sp4[cur2][j]!=n && a[sp4[cur2][j]]<mx && sp4[cur2][j]<C) cur2 = sp4[cur2][j], ans += (1<<j);
        if (cur2==-1 || cur2==n){
            cur = sp3[cur][0];
            tmp3++;
            continue;
        }
        cur2 = sp4[cur2][0], ans++;
        if (cur2<C || cur2>D){
            cur = sp3[cur][0];
            tmp3++;
            continue;
        }
        ret = min(ret, ans);

        cur = sp3[cur][0];
        tmp3++;
    }
    if (ret==1e9) return -1;
    return ret;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 28552 KB Output is correct
2 Correct 15 ms 28508 KB Output is correct
3 Execution timed out 4054 ms 140940 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28488 KB Output is correct
2 Correct 18 ms 28488 KB Output is correct
3 Correct 17 ms 28488 KB Output is correct
4 Correct 17 ms 28392 KB Output is correct
5 Correct 18 ms 28488 KB Output is correct
6 Correct 19 ms 28616 KB Output is correct
7 Correct 17 ms 28616 KB Output is correct
8 Correct 19 ms 28664 KB Output is correct
9 Correct 19 ms 28656 KB Output is correct
10 Correct 19 ms 28616 KB Output is correct
11 Correct 19 ms 28680 KB Output is correct
12 Correct 19 ms 28692 KB Output is correct
13 Correct 17 ms 28688 KB Output is correct
14 Correct 17 ms 28616 KB Output is correct
15 Correct 20 ms 28660 KB Output is correct
16 Correct 19 ms 28680 KB Output is correct
17 Correct 18 ms 28616 KB Output is correct
18 Correct 15 ms 28412 KB Output is correct
19 Correct 16 ms 28488 KB Output is correct
20 Correct 18 ms 28616 KB Output is correct
21 Correct 18 ms 28628 KB Output is correct
22 Correct 18 ms 28592 KB Output is correct
23 Correct 18 ms 28604 KB Output is correct
24 Correct 18 ms 28672 KB Output is correct
25 Correct 16 ms 28460 KB Output is correct
26 Correct 15 ms 28476 KB Output is correct
27 Correct 17 ms 28488 KB Output is correct
28 Correct 18 ms 28616 KB Output is correct
29 Correct 19 ms 28616 KB Output is correct
30 Correct 19 ms 28616 KB Output is correct
31 Correct 17 ms 28616 KB Output is correct
32 Correct 19 ms 28744 KB Output is correct
33 Correct 16 ms 28488 KB Output is correct
34 Correct 18 ms 28632 KB Output is correct
35 Correct 16 ms 28616 KB Output is correct
36 Correct 16 ms 28696 KB Output is correct
37 Correct 17 ms 28600 KB Output is correct
38 Correct 16 ms 28616 KB Output is correct
39 Correct 16 ms 28624 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28488 KB Output is correct
2 Correct 18 ms 28488 KB Output is correct
3 Correct 17 ms 28488 KB Output is correct
4 Correct 17 ms 28392 KB Output is correct
5 Correct 18 ms 28488 KB Output is correct
6 Correct 19 ms 28616 KB Output is correct
7 Correct 17 ms 28616 KB Output is correct
8 Correct 19 ms 28664 KB Output is correct
9 Correct 19 ms 28656 KB Output is correct
10 Correct 19 ms 28616 KB Output is correct
11 Correct 19 ms 28680 KB Output is correct
12 Correct 19 ms 28692 KB Output is correct
13 Correct 17 ms 28688 KB Output is correct
14 Correct 17 ms 28616 KB Output is correct
15 Correct 20 ms 28660 KB Output is correct
16 Correct 19 ms 28680 KB Output is correct
17 Correct 18 ms 28616 KB Output is correct
18 Correct 15 ms 28412 KB Output is correct
19 Correct 16 ms 28488 KB Output is correct
20 Correct 18 ms 28616 KB Output is correct
21 Correct 18 ms 28628 KB Output is correct
22 Correct 18 ms 28592 KB Output is correct
23 Correct 18 ms 28604 KB Output is correct
24 Correct 18 ms 28672 KB Output is correct
25 Correct 16 ms 28460 KB Output is correct
26 Correct 15 ms 28476 KB Output is correct
27 Correct 17 ms 28488 KB Output is correct
28 Correct 18 ms 28616 KB Output is correct
29 Correct 19 ms 28616 KB Output is correct
30 Correct 19 ms 28616 KB Output is correct
31 Correct 17 ms 28616 KB Output is correct
32 Correct 19 ms 28744 KB Output is correct
33 Correct 16 ms 28488 KB Output is correct
34 Correct 18 ms 28632 KB Output is correct
35 Correct 16 ms 28616 KB Output is correct
36 Correct 16 ms 28696 KB Output is correct
37 Correct 17 ms 28600 KB Output is correct
38 Correct 16 ms 28616 KB Output is correct
39 Correct 16 ms 28624 KB Output is correct
40 Correct 15 ms 28488 KB Output is correct
41 Correct 16 ms 28488 KB Output is correct
42 Correct 17 ms 28400 KB Output is correct
43 Correct 16 ms 28480 KB Output is correct
44 Correct 20 ms 28520 KB Output is correct
45 Correct 19 ms 28640 KB Output is correct
46 Correct 18 ms 28616 KB Output is correct
47 Correct 19 ms 28616 KB Output is correct
48 Correct 17 ms 28644 KB Output is correct
49 Correct 17 ms 28636 KB Output is correct
50 Correct 20 ms 28604 KB Output is correct
51 Correct 19 ms 28680 KB Output is correct
52 Correct 19 ms 28616 KB Output is correct
53 Correct 21 ms 28656 KB Output is correct
54 Correct 18 ms 28616 KB Output is correct
55 Correct 18 ms 28616 KB Output is correct
56 Correct 19 ms 28616 KB Output is correct
57 Correct 16 ms 28616 KB Output is correct
58 Correct 39 ms 29640 KB Output is correct
59 Correct 45 ms 29768 KB Output is correct
60 Correct 22 ms 29000 KB Output is correct
61 Correct 42 ms 29768 KB Output is correct
62 Correct 29 ms 28616 KB Output is correct
63 Correct 45 ms 29836 KB Output is correct
64 Correct 146 ms 29768 KB Output is correct
65 Correct 152 ms 29768 KB Output is correct
66 Correct 106 ms 29872 KB Output is correct
67 Correct 38 ms 29840 KB Output is correct
68 Correct 51 ms 29872 KB Output is correct
69 Correct 39 ms 29816 KB Output is correct
70 Correct 54 ms 29768 KB Output is correct
71 Correct 16 ms 28488 KB Output is correct
72 Correct 16 ms 28488 KB Output is correct
73 Correct 17 ms 28676 KB Output is correct
74 Correct 19 ms 28616 KB Output is correct
75 Correct 20 ms 28672 KB Output is correct
76 Correct 19 ms 28616 KB Output is correct
77 Correct 18 ms 28616 KB Output is correct
78 Correct 19 ms 28488 KB Output is correct
79 Correct 17 ms 28488 KB Output is correct
80 Correct 18 ms 28492 KB Output is correct
81 Correct 18 ms 28616 KB Output is correct
82 Correct 20 ms 28616 KB Output is correct
83 Correct 19 ms 28616 KB Output is correct
84 Correct 19 ms 28616 KB Output is correct
85 Correct 21 ms 28644 KB Output is correct
86 Correct 15 ms 28488 KB Output is correct
87 Correct 16 ms 28672 KB Output is correct
88 Correct 18 ms 28572 KB Output is correct
89 Correct 16 ms 28616 KB Output is correct
90 Correct 16 ms 28680 KB Output is correct
91 Correct 16 ms 28616 KB Output is correct
92 Correct 16 ms 28572 KB Output is correct
93 Correct 16 ms 28616 KB Output is correct
94 Correct 20 ms 28616 KB Output is correct
95 Correct 37 ms 29768 KB Output is correct
96 Correct 91 ms 29740 KB Output is correct
97 Correct 31 ms 29772 KB Output is correct
98 Correct 51 ms 29768 KB Output is correct
99 Correct 32 ms 29788 KB Output is correct
100 Correct 16 ms 28616 KB Output is correct
101 Correct 18 ms 29000 KB Output is correct
102 Correct 43 ms 29960 KB Output is correct
103 Correct 139 ms 29768 KB Output is correct
104 Correct 37 ms 29768 KB Output is correct
105 Correct 67 ms 29768 KB Output is correct
106 Correct 41 ms 29764 KB Output is correct
107 Correct 17 ms 28616 KB Output is correct
108 Correct 18 ms 29128 KB Output is correct
109 Correct 20 ms 29752 KB Output is correct
110 Correct 20 ms 29768 KB Output is correct
111 Correct 21 ms 29768 KB Output is correct
112 Correct 20 ms 29768 KB Output is correct
113 Correct 24 ms 29812 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28488 KB Output is correct
2 Correct 16 ms 28488 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Correct 16 ms 28436 KB Output is correct
5 Correct 469 ms 141996 KB Output is correct
6 Correct 602 ms 169876 KB Output is correct
7 Correct 311 ms 100416 KB Output is correct
8 Correct 585 ms 169880 KB Output is correct
9 Correct 94 ms 49552 KB Output is correct
10 Correct 583 ms 169988 KB Output is correct
11 Correct 659 ms 169992 KB Output is correct
12 Correct 585 ms 169932 KB Output is correct
13 Correct 614 ms 169896 KB Output is correct
14 Correct 578 ms 169920 KB Output is correct
15 Correct 710 ms 169892 KB Output is correct
16 Correct 585 ms 169888 KB Output is correct
17 Correct 596 ms 169900 KB Output is correct
18 Correct 16 ms 28488 KB Output is correct
19 Correct 16 ms 28624 KB Output is correct
20 Correct 17 ms 28616 KB Output is correct
21 Correct 16 ms 28616 KB Output is correct
22 Correct 17 ms 28616 KB Output is correct
23 Correct 16 ms 28584 KB Output is correct
24 Correct 16 ms 28616 KB Output is correct
25 Correct 16 ms 28616 KB Output is correct
26 Correct 18 ms 29120 KB Output is correct
27 Correct 21 ms 29760 KB Output is correct
28 Correct 21 ms 29852 KB Output is correct
29 Correct 21 ms 29760 KB Output is correct
30 Correct 24 ms 29768 KB Output is correct
31 Correct 23 ms 29768 KB Output is correct
32 Correct 16 ms 28488 KB Output is correct
33 Correct 577 ms 169672 KB Output is correct
34 Correct 592 ms 169864 KB Output is correct
35 Correct 614 ms 169952 KB Output is correct
36 Correct 587 ms 170024 KB Output is correct
37 Correct 681 ms 169936 KB Output is correct
38 Correct 593 ms 169964 KB Output is correct
39 Correct 16 ms 28488 KB Output is correct
40 Correct 344 ms 110004 KB Output is correct
41 Correct 589 ms 169864 KB Output is correct
42 Correct 616 ms 169932 KB Output is correct
43 Correct 584 ms 169920 KB Output is correct
44 Correct 712 ms 169920 KB Output is correct
45 Correct 582 ms 169936 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 28488 KB Output is correct
2 Correct 18 ms 28468 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Correct 493 ms 92740 KB Output is correct
5 Correct 1730 ms 169928 KB Output is correct
6 Correct 936 ms 51400 KB Output is correct
7 Correct 1683 ms 170048 KB Output is correct
8 Correct 935 ms 76660 KB Output is correct
9 Correct 1756 ms 169920 KB Output is correct
10 Execution timed out 4049 ms 169888 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 28488 KB Output is correct
2 Correct 18 ms 28468 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Correct 493 ms 92740 KB Output is correct
5 Correct 1730 ms 169928 KB Output is correct
6 Correct 936 ms 51400 KB Output is correct
7 Correct 1683 ms 170048 KB Output is correct
8 Correct 935 ms 76660 KB Output is correct
9 Correct 1756 ms 169920 KB Output is correct
10 Execution timed out 4049 ms 169888 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 28552 KB Output is correct
2 Correct 15 ms 28508 KB Output is correct
3 Execution timed out 4054 ms 140940 KB Time limit exceeded
4 Halted 0 ms 0 KB -