Submission #864811

#	Time	Username	Problem	Language	Result	Execution time	Memory
864811		hgmhc	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	808 ms	62908 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x, y) x = max(x, y)
#define mup(x, y) x = min(x, y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define ensure(...) if (!(__VA_ARGS__)) { fprintf(stderr, "Error in %dth line.", __LINE__), exit(-1); }

template <const int N>
struct segtree {
    int t[2*N]{};
    int &operator [] (int i){ return t[N+i]; }
    void build() {
        per(i,1,N-1) t[i] = max(t[2*i],t[2*i+1]);
    }
    int query(int a, int b) {
        int res = 0;
        for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) Mup(res,t[a]);
            if (~b&1) Mup(res,t[b]);
        }
        return res;
    }
};

const int N = 2e5;

vi adj[N];
int mj[N][20], lj[N][20], rj[N][20], Arg[N+1];
segtree<N> ds;

void construct_graph(int n, vi &H) {
    stack<int> S;
    rep(i,0,n-1) {
        while (not S.empty() and H[S.top()] < H[i]) S.pop();
        if (not S.empty()) adj[i].push_back(S.top());
        S.push(i);
    }
    while (not S.empty()) S.pop();
    per(i,0,n-1) {
        while (not S.empty() and H[S.top()] < H[i]) S.pop();
        if (not S.empty()) adj[i].push_back(S.top());
        S.push(i);
    }
}

void construct_sparsetable(int n, vi &H) {
    rep(i,0,n-1) {
        ensure(not adj[i].empty() or H[i] == n);
        if (adj[i].empty()) {
            mj[i][0] = lj[i][0] = rj[i][0] = i;
        }
        else if (siz(adj[i]) == 1) {
            mj[i][0] = adj[i][0];
            lj[i][0] = adj[i][0] < i ? adj[i][0] : i;
            rj[i][0] = adj[i][0] > i ? adj[i][0] : i;
        }
        else if (siz(adj[i]) == 2) {
            mj[i][0] = H[adj[i][0]] < H[adj[i][1]] ? adj[i][1] : adj[i][0];
            lj[i][0] = adj[i][0], rj[i][0] = adj[i][1];
            if (lj[i][0] > rj[i][0]) swap(lj[i][0],rj[i][0]);
        }
        else ensure(0);
    }
    rep(k,1,19) rep(i,0,n-1) {
        mj[i][k] = mj[mj[i][k-1]][k-1];
        lj[i][k] = lj[lj[i][k-1]][k-1];
        rj[i][k] = rj[rj[i][k-1]][k-1];
    }
}

void init(int N, vi H) {
    construct_graph(N, H);
    construct_sparsetable(N, H);
    rep(i,0,N-1) ds[i] = H[i], Arg[H[i]] = i;
    ds.build();
}


int A, B, C, D, hurdle;
const int INF = 1e9;

int dist(int x, int y) {
    if (ds.query(x,y-1) > ds[y]) return INF;
    int res = 0;
    if (x == y) return 0;
    per(i,0,19) while (ds[mj[x][i]] < ds[y]) x=mj[x][i], res += 1<<i;
    if (mj[x][0] == y) return res+1;
    per(i,0,19) while (x<rj[x][i] and ds[rj[x][i]] < ds[y]) x=rj[x][i], res += 1<<i;
    if (rj[x][0] == y) return res+1;
    ensure(0);
}

int tisd(int y, int x) {
    if (ds.query(y+1,x) > ds[y]) return INF;
    int res = 0;
    if (x == y) return 0;
    per(i,0,19) while (ds[mj[x][i]] < ds[y]) x=mj[x][i], res += 1<<i;
    if (mj[x][0] == y) return res+1;
    per(i,0,19) while (lj[x][i]<x and ds[lj[x][i]] < ds[y]) x=lj[x][i], res += 1<<i;
    if (lj[x][0] == y) return res+1;
    ensure(0);
}

int dist_lr(int a, int b, int y) {
    if (ds.query(b,y-1) > ds[y]) return INF;
    int res = 0, x = b;
    per(i,0,19) while (a<=lj[x][i]&&lj[x][i]<x and ds[lj[x][i]]<ds[y]) x=lj[x][i];
    return dist(x,y);
}

int dist_rl(int y, int a, int b) {
    if (ds.query(y+1,a) > ds[y]) return INF;
    int res = 0, x=a;
    per(i,0,19) while (x<rj[x][i]&&rj[x][i]<=b and ds[rj[x][i]]<ds[y]) x=rj[x][i];
    return tisd(y,x);
}

int ga() {
    return dist_lr(0,B,Arg[ds.query(B,C-1)])+1;
}

int na() {
    int x = B-1;
    per(i,0,19) while(A<=lj[x][i]&&lj[x][i]<x and ds[lj[x][i]]<hurdle) x=lj[x][i];
    if (A<=lj[x][0] && ds[lj[x][0]]>=hurdle) {
        if (ds.query(lj[x][0],C-1) <= ds.query(C,D)) return 1;
    }
    return INF;
}

int da() {
    int x = A-1;
    per(i,0,19) while(lj[x][i]<x and ds[lj[x][i]]<hurdle) x=lj[x][i];
    if (ds[lj[x][0]]>=hurdle) {
        return dist_rl(lj[x][0],A,B)+1;
    }
    return INF;
}

int minimum_jumps(int A, int B, int C, int D) {
    if (ds.query(B,C-1) > ds.query(C,D)) return -1;
    ::A = A, ::B = B, ::C = C, ::D = D;
    hurdle = ds.query(B,C-1);
    return min({ga(), na(), da()});
}

#ifdef LOCAL
int main()
{
    int N, Q;
    ensure(2 == scanf("%d %d", &N, &Q));
    std::vector<int> H(N);
    for (int i = 0; i < N; ++i)
    {
        ensure(1 == scanf("%d", &H[i]));
    }
    init(N, H);

    for (int i = 0; i < Q; ++i)
    {
        int A, B, C, D;
        ensure(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
        printf("%d\n", minimum_jumps(A, B, C, D));
    }
    return 0;
}
#endif

Compilation message (stderr)

jumps.cpp: In function 'int dist_lr(int, int, int)':
jumps.cpp:115:9: warning: unused variable 'res' [-Wunused-variable]
  115 |     int res = 0, x = b;
      |         ^~~
jumps.cpp: In function 'int dist_rl(int, int, int)':
jumps.cpp:122:9: warning: unused variable 'res' [-Wunused-variable]
  122 |     int res = 0, x=a;
      |         ^~~

• 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