oj.uz

답안 #696101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696101 2023-02-05T12:57:40 Z sharaelong 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1689 ms 53524 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

struct SegmentTree {
    int n, h;
    vector<pii> arr;
    SegmentTree(int _n) : n(_n) {
        h = Log2(n);
        n = 1 << h;
        arr.resize(2*n);
        for (int i=n; i<2*n; ++i) arr[i] = { 0, i-n };
        for (int i=n-1; i>=0; --i) arr[i] = { 0, arr[2*i].second };
    }

    void update(int pos, int c) {
        pos += n;
        arr[pos] = { c, pos-n };
        for (pos /= 2; pos > 0; pos /= 2) {
            arr[pos] = (arr[2*pos].first > arr[2*pos+1].first ? arr[2*pos] : arr[2*pos+1]);
        }
    }

    pii query(int l, int r) {
        l += n, r += n;
        pii ret = {0,-1};
        for (; l <= r; l/=2, r/=2) {
            if (l & 1) ret = (ret.first > arr[l].first ? ret : arr[l]), l++;
            if (~r & 1) ret = (ret.first > arr[r].first ? ret : arr[r]), r--;
        }
        return ret;
    }

    static int Log2(int x){
        int ret = 0;
        while (x > (1 << ret)) ret++;
        return ret;
    }
};

const int MAX_N = 2e5 + 1;

int n;
int h[MAX_N];
vector<int> adj[MAX_N];
int depth[MAX_N];
int large_sparse[18][MAX_N];
int sparse[18][MAX_N];
SegmentTree seg(MAX_N);

void dfs(int here) {
    for (int there: adj[here]) {
        depth[there] = depth[here] + 1;
        dfs(there);
    }
}

void init(int N, vector<int> H) {
    n = N;
    for (int i=0; i<n; ++i) h[i] = H[i];
    for (int i=0; i<n; ++i) seg.update(i, h[i]);
    
    vector<pii> nxt(n, {-1,-1});
    for (int i=0; i<n; ++i) {
        int l = i+1, r = n-1;
        while (l < r) {
            int m = (l+r)/2;
            if (seg.query(i+1, m).first > h[i]) {
                r = m;
            } else {
                l = m+1;
            }
        }
        if (l < n-1 || h[l] >= h[i]) nxt[i].second = l;
    }
    for (int i=0; i<n; ++i) {
        int l = 0, r = i-1;
        while (l < r) {
            int m = (l+r+1)/2;
            if (seg.query(m, i-1).first > h[i]) {
                l = m;
            } else {
                r = m-1;
            }
        }
        if (r > 0 || h[r] >= h[i]) nxt[i].first = r;
    }

    memset(sparse, -1, sizeof sparse);
    memset(large_sparse, -1, sizeof large_sparse);
    for (int i=0; i<n; ++i) {
        // cout << i << ' ' << nxt[i].first << ' ' << nxt[i].second << endl;
        if (nxt[i].first != -1 && nxt[i].second != -1) {
            large_sparse[0][i] = (h[nxt[i].first] > h[nxt[i].second] ? nxt[i].first : nxt[i].second);
            sparse[0][i] = (h[nxt[i].first] > h[nxt[i].second] ? nxt[i].second : nxt[i].first);
        } else {
            large_sparse[0][i] = (nxt[i].first == -1 ? nxt[i].second : nxt[i].first);
            sparse[0][i] = large_sparse[0][i];
        }
        if (sparse[0][i] != -1) adj[sparse[0][i]].push_back(i);
        // cout << i << ' ' << sparse[0][i] << ' ' << large_sparse[0][i] << endl;
    }
    for (int i=1; i<18; ++i) {
        for (int j=0; j<n; ++j) {
            if (sparse[i-1][j] != -1) sparse[i][j] = sparse[i-1][sparse[i-1][j]];
            if (large_sparse[i-1][j] != -1) large_sparse[i][j] = large_sparse[i-1][large_sparse[i-1][j]];
        }
    }
    dfs(seg.query(0, n-1).second);
}

bool is_reachable(int here, int par) {
    int d = max(0, depth[here] - depth[par]);
    for (int i=17; i>=0; --i) {
        if (d & (1 << i)) {
            here = sparse[i][here];
        }
    }
    return here == par;
}

int onetoone(int from, int to) {
    if (!is_reachable(from, to)) return -1;
    int ret = 0;
    for (int i=17; i>=0; --i) {
        if (large_sparse[i][from] != -1 && is_reachable(large_sparse[i][from], to)) {
            from = large_sparse[i][from];
            ret += (1 << i);
        }
    }
    return ret + depth[from] - depth[to];
}

int minimum_jumps(int A, int B, int C, int D) {
    auto[m, midx] = seg.query(B+1, C-1);
    if (seg.query(C, D).first < m) return -1;
    auto[highest, idx] = seg.query(A, B);
    if (highest < m) return onetoone(idx, midx) + 1;
    
    int l = A, r = B;
    while (l < r) {
        int mid = (l+r+1)/2;
        if (seg.query(mid, B).first > m) {
            l = mid;
        } else {
            r = mid-1;
        }
    }
    if (seg.query(C, D).first > h[l]) return 1;
    int from = seg.query(r+1, B).second;
    // cout << r << ' ' << from << endl;
    if (from == -1) return -1;
    return onetoone(from, m) + 1;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37320 KB Output is correct
2 Correct 16 ms 37360 KB Output is correct
3 Correct 550 ms 50104 KB Output is correct
4 Correct 1636 ms 53524 KB Output is correct
5 Correct 1286 ms 45352 KB Output is correct
6 Correct 1607 ms 53340 KB Output is correct
7 Correct 1276 ms 48256 KB Output is correct
8 Correct 1689 ms 53320 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 37200 KB Output is correct
2 Correct 15 ms 37200 KB Output is correct
3 Correct 15 ms 37292 KB Output is correct
4 Correct 15 ms 37200 KB Output is correct
5 Incorrect 17 ms 37248 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 37200 KB Output is correct
2 Correct 15 ms 37200 KB Output is correct
3 Correct 15 ms 37292 KB Output is correct
4 Correct 15 ms 37200 KB Output is correct
5 Incorrect 17 ms 37248 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37200 KB Output is correct
2 Correct 15 ms 37200 KB Output is correct
3 Correct 16 ms 37200 KB Output is correct
4 Correct 16 ms 37240 KB Output is correct
5 Correct 468 ms 44380 KB Output is correct
6 Correct 638 ms 46036 KB Output is correct
7 Correct 304 ms 41740 KB Output is correct
8 Correct 585 ms 46040 KB Output is correct
9 Correct 81 ms 38508 KB Output is correct
10 Correct 589 ms 46176 KB Output is correct
11 Correct 578 ms 53424 KB Output is correct
12 Incorrect 587 ms 52040 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37200 KB Output is correct
2 Correct 18 ms 37200 KB Output is correct
3 Correct 20 ms 37248 KB Output is correct
4 Incorrect 446 ms 41236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37200 KB Output is correct
2 Correct 18 ms 37200 KB Output is correct
3 Correct 20 ms 37248 KB Output is correct
4 Incorrect 446 ms 41236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 37320 KB Output is correct
2 Correct 16 ms 37360 KB Output is correct
3 Correct 550 ms 50104 KB Output is correct
4 Correct 1636 ms 53524 KB Output is correct
5 Correct 1286 ms 45352 KB Output is correct
6 Correct 1607 ms 53340 KB Output is correct
7 Correct 1276 ms 48256 KB Output is correct
8 Correct 1689 ms 53320 KB Output is correct
9 Correct 15 ms 37200 KB Output is correct
10 Correct 15 ms 37200 KB Output is correct
11 Correct 15 ms 37292 KB Output is correct
12 Correct 15 ms 37200 KB Output is correct
13 Incorrect 17 ms 37248 KB Output isn't correct
14 Halted 0 ms 0 KB -