Submission #1198106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198106		adiyer	밀림 점프 (APIO21_jumps)	C++20	0 / 100	117 ms	80892 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 11;

int n, tick;
int a[MAXN], l[MAXN], r[MAXN], d[MAXN], tin[MAXN], tout[MAXN];

pair < int, int > mx[MAXN][20], mn[MAXN][20];

bool was[MAXN], del[MAXN];

stack < int > s;

vector < int > g[MAXN];

pair < int, int > get(int l, int r){
    if(l > r) return {-1, -1};
    int k = __lg(r - l + 1);
    return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}

pair < int, int > get2(int l, int r){
    if(l > r) return {-1, -1};
    int k = __lg(r - l + 1);
    return min(mn[l][k], mn[r - (1 << k) + 1][k]);
}

void bfs(int s){
    queue < int > q;
    q.push(s), was[s] = 1;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int u : g[v])
            if(!was[u])
                was[u] = 1, d[u] = d[v] + 1, q.push(u);
    }
}

void dfs(int v){
    del[v] = 1, tin[v] = ++tick;
    for(int u : g[v])
        if(!del[u])
            dfs(u);
    tout[v] = tick;
}

bool parent(int x, int y){
    return tin[x] <= tin[y] && tout[y] <= tout[x];
}

void init(int N, vector < int > H) {
    n = N;
    for(int i = 0; i < N; i++) mx[i][0] = {H[i], i}, a[i] = H[i];
    for(int k = 1; k < 20; k++)
        for(int i = 0; i + (1 << k) - 1 < N; i++)
            mx[i][k] = max(mx[i][k - 1], mx[i + (1 << (k - 1))][k - 1]);
    for(int i = 0; i < N; i++){
        while(!s.empty() && a[i] > a[s.top()]) s.pop();
        l[i] = (s.empty() ? -1 : s.top()), s.push(i);
    }
    while(!s.empty()) s.pop();
    for(int i = N - 1; i >= 0; i--){
        while(!s.empty() && a[i] > a[s.top()]) s.pop();
        r[i] = (s.empty() ? -1 : s.top()), s.push(i);
    }
    for(int i = 0; i < N; i++){ 
        if(l[i] != -1) g[l[i]].push_back(i);
        if(r[i] != -1) g[r[i]].push_back(i);
    }
    vector < int > cur, nw;
    for(int i = 0; i < N; i++) cur.push_back(i);
    for(int rep = 0; rep < N; rep++){
        for(int i : cur)
            if(!was[i])
                nw.push_back(i);
        cur = nw, nw.clear();
        if(cur.empty()) break;
        int s = cur.back();
        for(int i : cur)
           if(a[i] > a[s]) 
            s = i;
        bfs(s);
        dfs(s);
    }
    for(int i = 0; i < N; i++) mn[i][0] = {d[i], i};
    for(int k = 1; k < 20; k++)
        for(int i = 0; i + (1 << k) - 1 < N; i++)
            mn[i][k] = min(mn[i][k - 1], mn[i + (1 << (k - 1))][k - 1]);
}

int minimum_jumps(int A, int B, int C, int D){
    if(!parent(get(C, D).second, get2(A, B).second)) return -1;
    return d[get2(A, B).second] - d[get(C, D).second];
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19