oj.uz

답안 #981578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981578 2024-05-13T10:55:17 Z Ghulam_Junaid 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1020 ms 311116 KB 
#include <bits/stdc++.h>
#include "jumps.h"

using namespace std;

const int MXN = 2e5 + 10;
const int T = 330;

int n, pos[MXN], to_left[MXN], to_right[MXN], dp[MXN][T + 1];
vector<int> seg[4 * MXN], h;
bool subtask1 = 1;

void build(int v = 1, int s = 0, int e = n){
    if (e - s == 1){
        seg[v] = {h[s]};
        return;
    }

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    build(lc, s, mid);
    build(rc, mid, e);

    seg[v] = seg[lc];
    for (int x : seg[rc])
        seg[v].push_back(x);

    sort(seg[v].begin(), seg[v].end());
}

int get(int l, int r, int x, int v = 1, int s = 0, int e = n){
    // int mx = -1;
    // for (int i = l; i < r; i ++)
    //     if (h[i] < x)
    //         mx = max(mx, h[i]);
    // return mx;

    if (e <= l || r <= s) return -1;
    if (l <= s && e <= r){
        if (x > seg[v].back())
            return seg[v].back();
        if (x <= seg[v][0])
            return -1;

        int lb = lower_bound(seg[v].begin(), seg[v].end(), x) - seg[v].begin();
        return seg[v][lb - 1];
    }

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    return max(get(l, r, x, lc, s, mid), get(l, r, x, rc, mid, e));
}

void init(int N, vector<int> H) {
    n = N;
    h = H;

    for (int i = 0; i < n; i ++)
        pos[h[i]] = i, subtask1 &= (h[i] == (i + 1));

    build();

    stack<int> S;
    for (int i = 0; i < n; i ++){
        while(S.size() and h[S.top()] <= h[i])
            S.pop();

        if (S.size())
            to_left[i] = S.top();
        else
            to_left[i] = i;
        
        S.push(i);
    }

    while (S.size())
        S.pop();

    for (int i = n - 1; i >= 0; i --){
        while (S.size() and h[S.top()] <= h[i])
            S.pop();

        if (S.size())
            to_right[i] = S.top();
        else
            to_right[i] = i;

        S.push(i);
    }

    // for (int i = 0; i < n; i ++){
    //     to_left[i] = to_right[i] = i;
    //     for (int j = i + 1; j < n; j ++){
    //         if (h[j] > h[i]){
    //             to_right[i] = j;
    //             break;
    //         }
    //     }
    //     for (int j = i - 1; j >= 0; j --){
    //         if (h[j] > h[i]){
    //             to_left[i] = j;
    //             break;
    //         }
    //     }
    // }

    for (int i = 0; i < n; i ++){
        dp[i][0] = i;
        for (int j = 1; j <= T; j ++){
            dp[i][j] = (h[to_left[dp[i][j - 1]]] > h[to_right[dp[i][j - 1]]]) ? to_left[dp[i][j - 1]] : to_right[dp[i][j - 1]];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (subtask1) return C - B;

    B++, D++;

    int mx = get(C, D, n + 1);
    
    int l = A - 1, r = B - 1;
    if (get(r, C, n + 1) > mx)
        return -1;
    while (r - l > 1){
        int mid = (l + r) / 2;
        if (get(mid, C, n + 1) > mx)
            l = mid;
        else
            r = mid;
    }

    int val = get(r, B, mx);

    if (val == -1)
        return -1;

    int st = pos[val];
    if (get(st, C, n + 1) > mx) return -1;

    int ope = 0;

    if (C + 1 == D){
        while (h[dp[st][T]] < h[C]){
            st = dp[st][T];
            ope += T;
        }
        while (st < C){
            st = to_right[st];
            ope++;
        }
    }
    else{
        while (st < C){
            ope++;
            int opt1 = to_left[st];
            int opt2 = to_right[st];

            if (opt2 >= C or h[opt2] > h[opt1] or h[opt1] > mx)
                st = opt2;
            else
                st = opt1;
        }
    }

    return ope;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 404 ms 253496 KB Output is correct
4 Correct 1020 ms 310952 KB Output is correct
5 Correct 724 ms 167852 KB Output is correct
6 Correct 965 ms 311116 KB Output is correct
7 Correct 731 ms 221116 KB Output is correct
8 Correct 975 ms 311092 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 6 ms 23128 KB Output is correct
4 Correct 5 ms 23128 KB Output is correct
5 Correct 5 ms 23128 KB Output is correct
6 Correct 6 ms 23164 KB Output is correct
7 Correct 6 ms 23128 KB Output is correct
8 Correct 7 ms 23128 KB Output is correct
9 Correct 5 ms 23380 KB Output is correct
10 Correct 6 ms 23124 KB Output is correct
11 Correct 7 ms 23128 KB Output is correct
12 Incorrect 6 ms 23128 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 6 ms 23128 KB Output is correct
4 Correct 5 ms 23128 KB Output is correct
5 Correct 5 ms 23128 KB Output is correct
6 Correct 6 ms 23164 KB Output is correct
7 Correct 6 ms 23128 KB Output is correct
8 Correct 7 ms 23128 KB Output is correct
9 Correct 5 ms 23380 KB Output is correct
10 Correct 6 ms 23124 KB Output is correct
11 Correct 7 ms 23128 KB Output is correct
12 Incorrect 6 ms 23128 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 23128 KB Output is correct
2 Correct 5 ms 23172 KB Output is correct
3 Correct 5 ms 23128 KB Output is correct
4 Correct 5 ms 23172 KB Output is correct
5 Correct 440 ms 255376 KB Output is correct
6 Correct 533 ms 310612 KB Output is correct
7 Correct 267 ms 169032 KB Output is correct
8 Correct 530 ms 310892 KB Output is correct
9 Correct 81 ms 66640 KB Output is correct
10 Correct 532 ms 310612 KB Output is correct
11 Correct 455 ms 310964 KB Output is correct
12 Correct 446 ms 310900 KB Output is correct
13 Correct 439 ms 310852 KB Output is correct
14 Correct 521 ms 310672 KB Output is correct
15 Incorrect 451 ms 310852 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 5 ms 23128 KB Output is correct
4 Incorrect 402 ms 154076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 5 ms 23128 KB Output is correct
4 Incorrect 402 ms 154076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 404 ms 253496 KB Output is correct
4 Correct 1020 ms 310952 KB Output is correct
5 Correct 724 ms 167852 KB Output is correct
6 Correct 965 ms 311116 KB Output is correct
7 Correct 731 ms 221116 KB Output is correct
8 Correct 975 ms 311092 KB Output is correct
9 Correct 5 ms 23128 KB Output is correct
10 Correct 5 ms 23128 KB Output is correct
11 Correct 6 ms 23128 KB Output is correct
12 Correct 5 ms 23128 KB Output is correct
13 Correct 5 ms 23128 KB Output is correct
14 Correct 6 ms 23164 KB Output is correct
15 Correct 6 ms 23128 KB Output is correct
16 Correct 7 ms 23128 KB Output is correct
17 Correct 5 ms 23380 KB Output is correct
18 Correct 6 ms 23124 KB Output is correct
19 Correct 7 ms 23128 KB Output is correct
20 Incorrect 6 ms 23128 KB Output isn't correct
21 Halted 0 ms 0 KB -