oj.uz

답안 #558610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558610 2022-05-07T15:28:38 Z pakhomovee 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1611 ms 208192 KB 
#include "jumps.h"

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int maxn = 1 << 20;

struct segTreeMax {
    pair<int, int> tree[maxn];
    
    void build(int i, int l, int r, vector<int> & h) {
        if (l + 1 == r) {
            tree[i] = { h[l], l };
            return;
        }
        int m = (l + r) / 2;
        build(i * 2 + 1, l, m, h);
        build(i * 2 + 2, m, r, h);
        tree[i] = max(tree[i * 2 + 1], tree[i * 2 + 2]);
    }
    
    pair<int, int> get(int i, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) {
            return { -1, -1 };
        }
        if (ql <= l && r <= qr) {
            return tree[i];
        }
        int m = (l + r) / 2;
        return max(get(i * 2 + 1, l, m, ql, qr), get(i * 2 + 2, m, r, ql, qr));
    }
};

struct segTreeMin {
    pair<int, int> tree[maxn];
    
    void build(int i, int l, int r, vector<int> & h) {
        if (l + 1 == r) {
            tree[i] = { h[l], l };
            return;
        }
        int m = (l + r) / 2;
        build(i * 2 + 1, l, m, h);
        build(i * 2 + 2, m, r, h);
        tree[i] = min(tree[i * 2 + 1], tree[i * 2 + 2]);
    }
    
    pair<int, int> get(int i, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) {
            return { 1e9, -1 };
        }
        if (ql <= l && r <= qr) {
            return tree[i];
        }
        int m = (l + r) / 2;
        return min(get(i * 2 + 1, l, m, ql, qr), get(i * 2 + 2, m, r, ql, qr));
    }
};

struct mst {
    vector<int> tree[maxn];
    
    void build(int i, int l, int r, int* h) {
        if (l + 1 == r) {
            tree[i] = { h[l] };
            return;
        }
        int m = (l + r) / 2;
        build(i * 2 + 1, l, m, h);
        build(i * 2 + 2, m, r, h);
        tree[i].resize(tree[i * 2 + 1].size() + tree[i * 2 + 2].size());
        merge(tree[i * 2 + 1].begin(), tree[i * 2 + 1].end(), tree[i * 2 + 2].begin(), tree[i * 2 + 2].end(), tree[i].begin());
    }
    
    int get(int i, int l, int r, int ql, int qr, int x) {
        if (qr <= l || r <= ql) {
            return -1e9;
        }
        if (ql <= l && r <= qr) {
            if (tree[i][0] > x) {
                return -1e9;
            }
            return *(--upper_bound(tree[i].begin(), tree[i].end(), x));
        }
        int m = (l + r) / 2;
        return max(get(i * 2 + 1, l, m, ql, qr, x), get(i * 2 + 2, m, r, ql, qr, x));
    }
};

segTreeMax st;
segTreeMin st1;
mst st2;
mst st3;
int upRight[20][maxn];
int upLeft[20][maxn];
vector<int> gLeft[maxn];
vector<int> gRight[maxn];
int hLeft[maxn];
int hRight[maxn];
int n;

void dfsLeft(int v, vector<bool> &used, int h) {
    used[v] = 1;
    hLeft[v] = h;
    for (int u : gLeft[v]) {
        dfsLeft(u, used, h - 1);
    }
}

void dfsRight(int v, vector<bool> &used, int h) {
    used[v] = 1;
    hRight[v] = h;
    for (int u : gRight[v]) {
        dfsRight(u, used, h - 1);
    }
}

void init(int N, std::vector<int> H) {
    n = N;
    st.build(0, 0, N, H);
    st1.build(0, 0, N, H);
    int HH[N];
    for (int i = 0; i < N; ++i) {
        HH[i] = H[i];
    }
    st3.build(0, 0, N, HH);
    vector<pair<int, int>> stk;
    for (int i = 0; i < N; ++i) {
        while (!stk.empty() && stk.back() < make_pair(H[i], i)) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            upLeft[0][i] = stk.back().second;
        } else {
            upLeft[0][i] = -1;
        }
        stk.push_back({ H[i], i });
    }
    stk.clear();
    for (int i = N - 1; i >= 0; --i) {
        while (!stk.empty() && stk.back() < make_pair(H[i], i)) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            upRight[0][i] = stk.back().second;
        } else {
            upRight[0][i] = -1;
        }
        stk.push_back({ H[i], i });
    }
    stk.clear();
    for (int j = 1; j < 20; ++j) {
        for (int i = N - 1; i >= 0; --i) {
            if (upLeft[j - 1][i] != -1) {
                upLeft[j][i] = upLeft[j - 1][upLeft[j - 1][i]];
            } else {
                upLeft[j][i] = -1;
            }
            if (upRight[j - 1][i] != -1) {
                upRight[j][i] = upRight[j - 1][upRight[j - 1][i]];
            } else {
                upRight[j][i] = -1;
            }
        }
    }
    
    vector<int> in(N, 0);
    for (int i = 0; i < N; ++i) {
        if (upLeft[0][i] != -1) {
            gLeft[upLeft[0][i]].push_back(i);
        }
        if (upRight[0][i] != -1) {
            gRight[i].push_back(upRight[0][i]);
            ++in[upRight[0][i]];
        }
    }
    vector<bool> usedLeft(N, false);
    vector<bool> usedRight(N, false);
    for (int i = 0; i < N; ++i) {
        if (!usedLeft[i]) {
            dfsLeft(i, usedLeft, 0);
        }
        if (!usedRight[i] && in[i] == 0) {
            dfsRight(i, usedRight, 0);
        }
    }
    for (int i = 0; i < N; ++i) {
        hRight[i] *= -1;
    }
    st2.build(0, 0, N, hRight);
}

int fromPointToSegment(int mid, int l, int r) {
    int ans = 0;
    for (int j = 19; j >= 0; --j) {
        if (upRight[j][mid] != -1 && upRight[j][mid] < l) {
            ans += (1 << j);
            mid = upRight[j][mid];
        }
    }
    mid = upRight[0][mid];
    if (mid <= r) {
        return ans + 1;
    }
    return -1e9;
}

int fromSegmentToPoint(int l, int r, int mid, int v) {
    int x = st2.get(0, 0, n, l, r + 1, hRight[mid]);
    if (x > hRight[mid]) {
        return -1e9;
    }
    return hRight[mid] - x;
}

int minimum_jumps(int A, int B, int C, int D) {
    auto [xmid, midpos] = st.get(0, 0, n, B + 1, C);
    int xleft = st1.get(0, 0, n, A, B + 1).first;
    int xright = st.get(0, 0, n, C, D + 1).first;
    if (xright < xmid || xleft > xright) {
        return -1;
    }
    int q = st3.get(0, 0, n, A, B + 1, xright);
    if (q > xmid) {
        return 1;
    }
    int ans = fromPointToSegment(midpos, C, D);
    ans += fromSegmentToPoint(A, B, midpos, xmid);
    if (ans < 0) {
        return -1;
    }
    return ans;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 99016 KB Output is correct
2 Correct 47 ms 99008 KB Output is correct
3 Correct 353 ms 187120 KB Output is correct
4 Correct 1611 ms 208112 KB Output is correct
5 Correct 1283 ms 153252 KB Output is correct
6 Correct 1496 ms 208192 KB Output is correct
7 Correct 1305 ms 175684 KB Output is correct
8 Correct 1441 ms 208080 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 99016 KB Output is correct
2 Correct 49 ms 99076 KB Output is correct
3 Correct 49 ms 99068 KB Output is correct
4 Correct 50 ms 99012 KB Output is correct
5 Incorrect 51 ms 99032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 99016 KB Output is correct
2 Correct 49 ms 99076 KB Output is correct
3 Correct 49 ms 99068 KB Output is correct
4 Correct 50 ms 99012 KB Output is correct
5 Incorrect 51 ms 99032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 99008 KB Output is correct
2 Correct 48 ms 99124 KB Output is correct
3 Correct 47 ms 99016 KB Output is correct
4 Correct 55 ms 99056 KB Output is correct
5 Incorrect 253 ms 181836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 99044 KB Output is correct
2 Correct 49 ms 99016 KB Output is correct
3 Correct 47 ms 99060 KB Output is correct
4 Incorrect 399 ms 145068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 99044 KB Output is correct
2 Correct 49 ms 99016 KB Output is correct
3 Correct 47 ms 99060 KB Output is correct
4 Incorrect 399 ms 145068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 99016 KB Output is correct
2 Correct 47 ms 99008 KB Output is correct
3 Correct 353 ms 187120 KB Output is correct
4 Correct 1611 ms 208112 KB Output is correct
5 Correct 1283 ms 153252 KB Output is correct
6 Correct 1496 ms 208192 KB Output is correct
7 Correct 1305 ms 175684 KB Output is correct
8 Correct 1441 ms 208080 KB Output is correct
9 Correct 48 ms 99016 KB Output is correct
10 Correct 49 ms 99076 KB Output is correct
11 Correct 49 ms 99068 KB Output is correct
12 Correct 50 ms 99012 KB Output is correct
13 Incorrect 51 ms 99032 KB Output isn't correct
14 Halted 0 ms 0 KB -