제출 #1195007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195007		ainunnajib	밀림 점프 (APIO21_jumps)	C++20	컴파일 에러	0 ms	0 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const int MAXLOG = 18;
const int MAXNODE = 200000 * 20; // ~4e6, but we allocate up to 20e6 nodes for safety

int N, Q;
int H[MAXN];
int Lgr[MAXN], Rgr[MAXN];
int parentArr[MAXN], skipArr[MAXN];
vector<int> children[MAXN];
int depthArr[MAXN];
int tin[MAXN], tout[MAXN], timer_dfs = 0;

// For binary lifting on skip edges
int up[MAXN][MAXLOG];
int skipLen[MAXN][MAXLOG];

// For RMQ on H
int stIdx[MAXLOG][MAXN];
int lg2[MAXN+1];

// Segment-tree-of-segment-trees for 2D query (index range & subtree range)
int *root;
struct SegNode { int l, r, mh, mi; } seg[20000000];
int segCnt = 1;

// Update the inner (tin-dimension) segtree
int updateTin(int s, int tl, int tr, int pos, int h, int idx) {
    if (!s) {
        s = segCnt++;
        seg[s].l = seg[s].r = 0;
        seg[s].mh = h;
        seg[s].mi = idx;
    } else if (h > seg[s].mh || (h == seg[s].mh && idx < seg[s].mi)) {
        seg[s].mh = h;
        seg[s].mi = idx;
    }
    if (tl == tr) return s;
    int mid = (tl + tr) >> 1;
    if (pos <= mid)
        seg[s].l = updateTin(seg[s].l, tl, mid, pos, h, idx);
    else
        seg[s].r = updateTin(seg[s].r, mid+1, tr, pos, h, idx);
    return s;
}

// Update the outer (index-dimension) segtree
void updateIdx(int id, int l, int r, int pos, int tinpos, int h, int idx) {
    root[id] = updateTin(root[id], 1, N, tinpos, h, idx);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) updateIdx(id<<1, l, mid, pos, tinpos, h, idx);
    else           updateIdx(id<<1|1, mid+1, r, pos, tinpos, h, idx);
}

// Query the inner segtree for max (h,idx)
pair<int,int> queryTin(int s, int tl, int tr, int ql, int qr) {
    if (!s || qr < tl || tr < ql) return {-1, -1};
    if (ql <= tl && tr <= qr) return {seg[s].mh, seg[s].mi};
    int mid = (tl + tr) >> 1;
    auto a = queryTin(seg[s].l, tl, mid, ql, qr);
    auto b = queryTin(seg[s].r, mid+1, tr, ql, qr);
    if (a.first > b.first) return a;
    if (b.first > a.first) return b;
    if (a.second < 0) return b;
    if (b.second < 0) return a;
    return a.second < b.second ? a : b;
}

// Query the outer segtree on [ql,qr] and inner on [tl,tr]
pair<int,int> queryIdx(int id, int l, int r, int ql, int qr, int tl, int tr) {
    if (qr < l || r < ql) return {-1, -1};
    if (ql <= l && r <= qr) {
        return queryTin(root[id], 1, N, tl, tr);
    }
    int mid = (l + r) >> 1;
    auto a = queryIdx(id<<1,   l, mid, ql, qr, tl, tr);
    auto b = queryIdx(id<<1|1, mid+1, r, ql, qr, tl, tr);
    if (a.first > b.first) return a;
    if (b.first > a.first) return b;
    if (a.second < 0) return b;
    if (b.second < 0) return a;
    return a.second < b.second ? a : b;
}

// Build nearest-greater arrays
void buildNearest() {
    stack<int> st;
    for (int i = 0; i < N; i++) {
        while (!st.empty() && H[st.top()] < H[i]) st.pop();
        Lgr[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = N-1; i >= 0; i--) {
        while (!st.empty() && H[st.top()] < H[i]) st.pop();
        Rgr[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q;
    for (int i = 0; i < N; i++) cin >> H[i];
    buildNearest();

    int rootIdx = 0;
    // Determine parent & skip for each node in the Cartesian tree
    for (int i = 0; i < N; i++) {
        int l = Lgr[i], r = Rgr[i];
        if (l<0 && r<0) {
            parentArr[i] = -1;
            skipArr[i] = -1;
            rootIdx = i;
        } else if (l<0) {
            parentArr[i] = r;
            skipArr[i] = -1;
        } else if (r<0) {
            parentArr[i] = l;
            skipArr[i] = -1;
        } else if (H[l] < H[r]) {
            parentArr[i] = l;
            skipArr[i] = r;
        } else {
            parentArr[i] = r;
            skipArr[i] = l;
        }
    }
    // Build adjacency in Cartesian tree
    for (int i = 0; i < N; i++) {
        if (parentArr[i] >= 0)
            children[parentArr[i]].push_back(i);
    }

    // Iterative DFS to compute tin, tout, depth
    vector<int> st_node, st_ptr(N);
    st_node.push_back(rootIdx);
    depthArr[rootIdx] = 0;
    st_ptr[rootIdx] = 0;
    while (!st_node.empty()) {
        int u = st_node.back();
        if (st_ptr[u] == 0) tin[u] = ++timer_dfs;
        if (st_ptr[u] < (int)children[u].size()) {
            int v = children[u][st_ptr[u]++];
            depthArr[v] = depthArr[u] + 1;
            st_ptr[v] = 0;
            st_node.push_back(v);
        } else {
            tout[u] = timer_dfs;
            st_node.pop_back();
        }
    }

    // Prepare binary lifting for skip edges
    for (int i = 0; i < N; i++) {
        up[i][0] = skipArr[i] >= 0 ? skipArr[i] : -1;
        skipLen[i][0] = skipArr[i] >= 0 ? 1 : 0;
    }
    for (int k = 1; k < MAXLOG; k++) {
        for (int i = 0; i < N; i++) {
            int m = up[i][k-1];
            if (m >= 0) {
                up[i][k] = up[m][k-1];
                skipLen[i][k] = skipLen[i][k-1] + skipLen[m][k-1];
            } else {
                up[i][k] = -1;
                skipLen[i][k] = skipLen[i][k-1];
            }
        }
    }

    // Build sparse table for RMQ on H
    lg2[1] = 0;
    for (int i = 2; i <= N; i++) lg2[i] = lg2[i>>1] + 1;
    for (int i = 0; i < N; i++) stIdx[0][i] = i;
    for (int k = 1; k < MAXLOG; k++) {
        for (int i = 0; i + (1<<k) <= N; i++) {
            int a = stIdx[k-1][i];
            int b = stIdx[k-1][i + (1<<(k-1))];
            stIdx[k][i] = (H[a] >= H[b] ? a : b);
        }
    }
    auto rmqIdx = [&](int l, int r){
        int len = r - l + 1;
        int k = lg2[len];
        int a = stIdx[k][l];
        int b = stIdx[k][r - (1<<k) + 1];
        return H[a] >= H[b] ? a : b;
    };

    // Build 2D segment tree
    root = new int[4*N]();
    for (int i = 0; i < N; i++) {
        updateIdx(1, 0, N-1, i, tin[i], H[i], i);
    }

    // Answer queries
    while (Q--) {
        int A,B,C,D;
        cin >> A >> B >> C >> D;
        // find target y = index of max H in [C,D]
        int y = rmqIdx(C, D);
        // find best source s in [A,B] ∩ subtree(y)
        auto qr = queryIdx(1, 0, N-1, A, B, tin[y], tout[y]);
        int sidx = qr.second;
        if (sidx < 0) {
            cout << "-1\n";
            continue;
        }
        // compute minimal jumps from sidx up to y
        int cur = sidx, ans = 0;
        for (int k = MAXLOG-1; k >= 0; k--) {
            int nxt = (cur>=0 ? up[cur][k] : -1);
            if (nxt >= 0 && depthArr[nxt] >= depthArr[y]) {
                ans += skipLen[cur][k];
                cur = nxt;
            }
        }
        // finish with parent-by-one jumps
        ans += depthArr[cur] - depthArr[y];
        cout << ans << "\n";
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccow7sGU.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccwfz15l.o:jumps.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccow7sGU.o: in function `main':
stub.cpp:(.text.startup+0x15d): undefined reference to `init(int, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: stub.cpp:(.text.startup+0x1b1): undefined reference to `minimum_jumps(int, int, int, int)'
collect2: error: ld returned 1 exit status