제출 #925172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925172		TAhmed33	밀림 점프 (APIO21_jumps)	C++17	100 / 100	1564 ms	49964 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
int a[MAXN], prv[MAXN], nxt[MAXN], n;
int dp[19][MAXN], dp2[19][MAXN], dp3[19][MAXN];
void init (int N, vector <int> h) {
	n = N;
	for (int i = 0; i < n; i++) a[i + 1] = h[i];
	stack <int> cur;
	cur.push(1);
	for (int i = 2; i <= n; i++) {
		while (!cur.empty() && a[i] > a[cur.top()]) {
			nxt[cur.top()] = i;
			cur.pop();
		}
		cur.push(i);
	}
	while (!cur.empty()) {
		nxt[cur.top()] = 0;
		cur.pop();
	}
	cur.push(n);
	for (int i = n - 1; i >= 1; i--) {
		while (!cur.empty() && a[i] > a[cur.top()]) {
			prv[cur.top()] = i;
			cur.pop();
		}
		cur.push(i);
	}
	while (!cur.empty()) {
		prv[cur.top()] = 0;
		cur.pop();
	}
    for (int i = 1; i <= n; i++) {
        dp2[0][i] = prv[i];
        dp3[0][i] = nxt[i];
        if (prv[i] && nxt[i] && a[prv[i]] > a[nxt[i]]) {
            dp[0][i] = prv[i];
        } else if (prv[i] && nxt[i] && a[prv[i]] < a[nxt[i]]) {
            dp[0][i] = nxt[i];
        }
    }
    for (int i = 1; i < 19; i++) {
        for (int j = 1; j <= n; j++) {
            dp2[i][j] = dp2[i - 1][dp2[i - 1][j]];
            dp3[i][j] = dp3[i - 1][dp3[i - 1][j]];
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }
}
int jump (int a, int b) {
    for (int i = 18; i >= 0; i--) {
        if (b & (1 << i)) {
            a = dp[i][a];
        }
    }
    return a;
}
int jump2 (int a, int b) {
    for (int i = 18; i >= 0; i--) {
        if (b & (1 << i)) {
            a = dp2[i][a];
        }
    }
    return a;
}
int jump3 (int a, int b) {
    for (int i = 18; i >= 0; i--) {
        if (b & (1 << i)) {
            a = dp3[i][a];
        }
    }
    return a;
}
int minimum_jumps (int a, int b, int c, int d) {
    a++; b++; c++; d++;
    int l = 0, r = n, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int x = jump2(b, mid);
        if (x == 0 || x < a) {
            r = mid - 1; continue;
        }
        if (!nxt[x] || nxt[x] > d) {
            r = mid - 1; continue;
        }
        l = mid + 1; ans = mid;
    }
    if (ans == -1) return -1;
    int cur = jump2(b, ans);
   //cout << cur << '\n';
    l = 0, r = n; int ans2 = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int x = jump(cur, mid);
        //cout << mid << " | " << x << '\n';
        if (x == 0) {
            r = mid - 1; continue;
        }
       // cout << mid << " n\n";
       // cout << nxt[x] << " " << c << " " << mid << '\n';
        if (nxt[x] && nxt[x] < c) {
            l = mid + 1; ans2 = mid; continue;
        }
        r = mid - 1;
    }
   // cout << ans2 << '\n';
    if (true) {
        int u = jump(cur, ans2 + 1);
        if (u) {
            if (nxt[u] && nxt[u] <= d) ans2++;
        }
    }
    int cur2 = jump(cur, ans2);
    //cout << cur2 << '\n';
// cout << cur2 << '\n'; //cout << ans2 << '\n';
    l = 0, r = n; int ans3 = -1;
   // cout << nxt[cur2] << '\n';
   // cout << nxt[nxt[cur2]] << '\n';
   // cout << nxt[nxt[nxt[cur2]]] << '\n';
    /*for (int i = 0; i <= 20; i++) {
        cout << i << ": " << jump3(cur2, i) << '\n';
    }*/
    while (l <= r) {
        int mid = (l + r) >> 1;
        int x = jump3(cur2, mid);
        //cout << c << " " << x << " | " << mid << '\n';
        if (!x || x >= c) {
            r = mid - 1; ans3 = mid;
        } else {
            l = mid + 1;
        }
    }
    //cout << ans3 << '\n';
    if (ans3 == -1) return -1;
    int cur3 = jump3(cur2, ans3);
    if (!cur3) return -1;
    //cout << cur3 << '\n';
    if (cur3 > d) return -1;
    return ans2 + ans3;
}

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