oj.uz

Submission #558623

# Submission time Handle Problem Language Result Execution time Memory
558623 2022-05-07T16:15:20 Z pakhomovee Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 208132 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);
}

const int inf = 1e9;

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 (l <= mid && mid <= r) {
        return ans + 1;
    }
    return inf;
}

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 inf;
    }
    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 ans = inf;
    for (int i = A; i <= B; ++i) {
        ans = min(ans, fromPointToSegment(i, C, D));
    }
    if (ans == inf) {
        return -1;
    }
    return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 99016 KB Output is correct
2 Correct 48 ms 99036 KB Output is correct
3 Execution timed out 4072 ms 187112 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 99100 KB Output is correct
2 Correct 46 ms 99088 KB Output is correct
3 Correct 45 ms 99024 KB Output is correct
4 Correct 46 ms 99024 KB Output is correct
5 Correct 48 ms 99080 KB Output is correct
6 Incorrect 53 ms 99108 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 99100 KB Output is correct
2 Correct 46 ms 99088 KB Output is correct
3 Correct 45 ms 99024 KB Output is correct
4 Correct 46 ms 99024 KB Output is correct
5 Correct 48 ms 99080 KB Output is correct
6 Incorrect 53 ms 99108 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 99048 KB Output is correct
2 Correct 47 ms 98996 KB Output is correct
3 Correct 46 ms 99104 KB Output is correct
4 Correct 47 ms 99080 KB Output is correct
5 Correct 245 ms 181868 KB Output is correct
6 Correct 254 ms 200488 KB Output is correct
7 Correct 155 ms 150176 KB Output is correct
8 Correct 270 ms 200388 KB Output is correct
9 Correct 76 ms 113524 KB Output is correct
10 Correct 295 ms 200456 KB Output is correct
11 Correct 244 ms 208132 KB Output is correct
12 Correct 234 ms 205684 KB Output is correct
13 Incorrect 232 ms 205160 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 99016 KB Output is correct
2 Correct 47 ms 99124 KB Output is correct
3 Correct 49 ms 99016 KB Output is correct
4 Incorrect 376 ms 145044 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 99016 KB Output is correct
2 Correct 47 ms 99124 KB Output is correct
3 Correct 49 ms 99016 KB Output is correct
4 Incorrect 376 ms 145044 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 99016 KB Output is correct
2 Correct 48 ms 99036 KB Output is correct
3 Execution timed out 4072 ms 187112 KB Time limit exceeded
4 Halted 0 ms 0 KB -