oj.uz

Submission #558621

# Submission time Handle Problem Language Result Execution time Memory
558621 2022-05-07T16:09:57 Z pakhomovee Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 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);
    }
}
const int inf = 1e9;
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 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 -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 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 50 ms 99016 KB Output is correct
2 Correct 48 ms 99016 KB Output is correct
3 Execution timed out 4033 ms 187176 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 99028 KB Output is correct
2 Correct 47 ms 99020 KB Output is correct
3 Correct 47 ms 99112 KB Output is correct
4 Correct 48 ms 99044 KB Output is correct
5 Incorrect 52 ms 99016 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 99028 KB Output is correct
2 Correct 47 ms 99020 KB Output is correct
3 Correct 47 ms 99112 KB Output is correct
4 Correct 48 ms 99044 KB Output is correct
5 Incorrect 52 ms 99016 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 99072 KB Output is correct
2 Correct 52 ms 99016 KB Output is correct
3 Correct 51 ms 99104 KB Output is correct
4 Correct 48 ms 99068 KB Output is correct
5 Correct 256 ms 181896 KB Output is correct
6 Correct 255 ms 200460 KB Output is correct
7 Correct 149 ms 150240 KB Output is correct
8 Correct 305 ms 200468 KB Output is correct
9 Correct 76 ms 113588 KB Output is correct
10 Correct 316 ms 200452 KB Output is correct
11 Correct 238 ms 208192 KB Output is correct
12 Correct 235 ms 205556 KB Output is correct
13 Incorrect 244 ms 205176 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 99072 KB Output is correct
2 Correct 46 ms 99100 KB Output is correct
3 Correct 49 ms 99124 KB Output is correct
4 Incorrect 357 ms 144996 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 99072 KB Output is correct
2 Correct 46 ms 99100 KB Output is correct
3 Correct 49 ms 99124 KB Output is correct
4 Incorrect 357 ms 144996 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 99016 KB Output is correct
2 Correct 48 ms 99016 KB Output is correct
3 Execution timed out 4033 ms 187176 KB Time limit exceeded
4 Halted 0 ms 0 KB -