제출 #1191867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191867		duyngadocton	밀림 점프 (APIO21_jumps)	C++20	4 / 100	622 ms	87476 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ii pair<int,int>
#define ll long long
#define pb push_back
#define eb emplace_back

const int MAX = (int) 2e5;
const int inf = (int) 1e9;

int n, h[MAX + 5];
ii mx[25][MAX + 5];
int lg[MAX + 5];
int fmx[25][MAX + 5];
int posmax[25][MAX + 5];
int fnxt[25][MAX + 5];
int pre[MAX + 5], nxt[MAX + 5];
int f[25][MAX + 5];

int getmax(int l, int r) {
    int k = lg[r - l + 1];
    return max(mx[k][l], mx[k][r - (1 << k) + 1]).se;
}

void build() {
    pre[0] = 0, nxt[n + 1] = n + 1;
    h[0] = h[n + 1] = inf;
    for(int i = 1; i <= n; ++i) {
        int j = i - 1;
        while(j > 0 && h[j] <= h[i]) j = pre[j];
        pre[i] = j;
    }
    for(int i = n; i >= 1; --i) {
        int j = i + 1;
        while(j <= n && h[j] <= h[i]) j = nxt[j];
        nxt[i] = j;
    }
    for(int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
    for(int i = 1; i <= n; ++i) mx[0][i] = ii(h[i], i);
    for(int k = 1; k <= lg[n]; ++k)
        for(int i = 1; i + (1 << k) - 1 <= n; ++i) mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);
    for(int i = 1; i <= n; ++i) {
        int ptr = 0;
        if(pre[i] == 0 && nxt[i] == n + 1) ptr = 0;
        else if(pre[i] == 0) ptr = nxt[i];
        else if(nxt[i] == n + 1) ptr = pre[i];
        else ptr = (h[pre[i]] > h[nxt[i]]) ? pre[i] : nxt[i];
        fmx[0][i] = ptr;
        posmax[0][i] = ptr;
        f[0][i] = nxt[ptr];
    }
    for(int k = 1; k <= lg[n]; ++k)
        for(int i = 1; i <= n; ++i) fmx[k][i] = fmx[k - 1][fmx[k - 1][i]], posmax[k][i] = max(posmax[k - 1][i], posmax[k - 1][fmx[k - 1][i]]), f[k][i] = max(f[k - 1][i], f[k - 1][fmx[k - 1][i]]);
    for(int i = 1; i <= n; ++i) fnxt[0][i] = nxt[i];
    for(int k = 1; k <= lg[n]; ++k)
        for(int i = 1; i <= n; ++i) fnxt[k][i] = fnxt[k - 1][fnxt[k - 1][i]];
}

void init(int N, vector<int> H) {
    n = N;
    for(int i = 1; i <= n; ++i) h[i] = H[i - 1];
    build();
}

int sub3(int A, int B, int C, int D) {
    int pos = getmax(C, D);
    int lo = A - 1, hi = B;
    while(hi - lo > 1) {
        int mid = lo + hi >> 1;
        if(h[getmax(mid, B)] > h[pos]) lo = mid;
        else hi = mid;
    }
    if(h[getmax(hi, pos)] > h[pos]) return -1;
    int start = getmax(hi, B);
    int cur = start;
    int dem = 0;
    int ans = 0;
    for(int k = lg[n]; k >= 0; --k) if(h[fnxt[k][cur]] <= h[pos] && cur < C) cur = fnxt[k][cur], ans += (1 << k);
    cur = start;
    for(int k = lg[n]; k >= 0; --k) {
        if(posmax[k][cur] < C && h[fmx[k][cur]] < h[pos]) cur = fmx[k][cur], dem += (1 << k);
    }
    if(h[fmx[0][cur]] > h[pos]) {
        for(int k = lg[n]; k >= 0; --k) if(h[fnxt[k][cur]] <= h[pos] && cur < C) cur = fnxt[k][cur], dem += (1 << k);
    }
    else {
        dem += 1;
    }
    dem = min(ans, dem);
    ans = 0, cur = start;
    for(int k = lg[n]; k >= 0; --k) if(posmax[k][cur] < C && h[fmx[k][cur]] < h[pos] && f[k][cur] < C) cur = fmx[k][cur], ans += (1 << k);
    cur = fmx[0][cur];
    ++ans;
    if(nxt[cur] >= C) dem = min(dem, ans + 1);
    return dem;
}

int minimum_jumps(int A, int B, int C, int D) {
    return sub3(A + 1, B + 1, C + 1, D + 1);
}

• Subtask 1: 4 / 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