제출 #1118834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118834		Zero_OP	밀림 점프 (APIO21_jumps)	C++14	0 / 100	29 ms	3156 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e3 + 5;
const int inf = 1e9;

int N, H[MAX];
vector<int> adj[MAX];

struct RMQ{
    vector<vector<int>> rmq;

    RMQ(vector<int>& a) : rmq(){
        int N = (int)a.size();
        int L = 32 - __builtin_clz(N);
        rmq.emplace_back(a);
        for(int i = 1; i < L; ++i){
            rmq.emplace_back(N - (1 << i) + 1);
            for(int j = 0; j + (1 << i) <= N; ++j){
                rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    int query(int l, int r){
        int k = 31 - __builtin_clz(r - l + 1);
        return min(rmq[k][l], rmq[k][r - (1 << k) + 1]);
    }
};

vector<RMQ> rmqs;

vector<int> bfs(int s){
    vector<int> d(N, inf);
    queue<int> q;
    q.push(s);
    d[s] = 0;

    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto v : adj[u]){
            if(d[v] == inf){
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }

    return d;
}

void init(int _N, vector<int> _H){
    N = _N;
    for(int i = 0; i < N; ++i) H[i] = _H[i];

    stack<int> st;
    for(int i = 0; i < N; ++i){
        while(!st.empty() && H[st.top()] <= H[i]) st.pop();
        if(!st.empty()) adj[i].emplace_back(st.top());
        st.push(i);
    }

    stack<int>().swap(st);
    for(int i = N - 1; i >= 0; --i){
        while(!st.empty() && H[st.top()] <= H[i]) st.pop();
        if(!st.empty()) adj[i].emplace_back(st.top());
        st.push(i);
    }

    for(int i = 0; i < N; ++i){
        vector<int> d = bfs(i);
        rmqs.emplace_back(RMQ(d));
    }
}

int minimum_jumps(int a, int b, int c, int d){
    int cur = inf;
    for(int i = a; i <= b; ++i){
        cur = min(cur, rmqs[i].query(c, d));
    }

  	//really somehow ?? I gonna proof later
    int best = -1;
    for(int i = a; i <= b; ++i){
        if(best == -1 || H[best] < H[i]){
            best = i;
        }
    }

    int check = rmqs[best].query(c, d);

    assert(cur == check);
    return (check == inf ? -1 : check);
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.ans", "w", stdout);

    int N, Q;
    cin >> N >> Q;

    vector<int> H(N);
    for(int i = 0; i < N; ++i){
        cin >> H[i];
    }

    init(N, H);

    for(int i = 0; i < Q; ++i){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << minimum_jumps(a, b, c, d) << '\n';
    }

    return 0;
}
#endif //LOCAL

• 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