제출 #471914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471914		qwerasdfzxcl	밀림 점프 (APIO21_jumps)	C++14	33 / 100	4054 ms	170048 KiB

jumps

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

using namespace std;
typedef long long ll;
vector<int> sp1[200200], sp2[200200], sp3[200200], sp4[200200], a;
int n, l[200200], r[200200], INV[200200];
struct MST{
    vector<int> tree[400400];
    int sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i].push_back(a[i-sz]);
        for (int i=sz-1;i;i--){
            tree[i].resize(tree[i<<1].size()+tree[i<<1|1].size());
            merge(tree[i<<1].begin(), tree[i<<1].end(), tree[i<<1|1].begin(), tree[i<<1|1].end(), tree[i].begin());
        }
    }
    int query(int l, int r, int x){
        int ret = -1;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                auto iter = lower_bound(tree[l].begin(), tree[l].end(), x);
                if (iter!=tree[l].begin()) ret = max(ret, *(--iter));
                l++;
            }
            if (r&1){
                --r;
                auto iter = lower_bound(tree[r].begin(), tree[r].end(), x);
                if (iter!=tree[r].begin()) ret = max(ret, *(--iter));
            }
        }
        return ret;
    }
    int query2(int l, int r){
        int ret = -1;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                ret = max(ret, tree[l].back());
                l++;
            }
            if (r&1){
                --r;
                ret = max(ret, tree[r].back());
            }
        }
        return ret;
    }
}tree;

int geth(int x){
    if (x<0) return -1e9;
    if (x>=n) return -1e9;
    return a[x];
}

void init(int N, std::vector<int> H) {
    n = N, a = H;
    for (int i=0;i<n;i++){
        INV[H[i]] = i;
        sp1[i].push_back(H[i]);
        sp2[i].push_back(H[i]);
    }
    for (int j=1;j<20;j++){
        for (int i=0;i<n;i++){
            if (i-(1<<j)+1<0) sp1[i].push_back(-1);
            else sp1[i].push_back(max(sp1[i][j-1], sp1[i-(1<<(j-1))][j-1]));
            if (i+(1<<j)-1>=n) sp2[i].push_back(-1);
            else sp2[i].push_back(max(sp2[i][j-1], sp2[i+(1<<(j-1))][j-1]));
        }
    }
    for (int i=0;i<n;i++){
        int cur = i-1, cur2 = -1e9;
        for (int j=19;j>=0;j--) if (cur!=-1 && sp1[cur][j]!=-1 && max(cur2, sp1[cur][j])<H[i]){
            cur2 = max(cur2, sp1[cur][j]);
            cur -= (1<<j);
        }
        l[i] = cur; cur = i+1, cur2 = -1e9;
        for (int j=19;j>=0;j--) if (cur!=n && sp2[cur][j]!=-1 && sp2[cur][j]<H[i]){
            cur2 = max(cur2, sp1[cur][j]);
            cur += (1<<j);
        }
        r[i] = cur;
        if (geth(l[i])>=geth(r[i])) sp3[i].push_back(l[i]);
        else sp3[i].push_back(r[i]);
        sp4[i].push_back(r[i]);
        //printf("%d %d\n", l[i], r[i]);
    }
    for (int j=1;j<20;j++){
        for (int i=0;i<n;i++){
            if (sp3[i][j-1]==-1) sp3[i].push_back(-1);
            else sp3[i].push_back(sp3[sp3[i][j-1]][j-1]);
            if (sp4[i][j-1]==n) sp4[i].push_back(n);
            else sp4[i].push_back(sp4[sp4[i][j-1]][j-1]);
        }
    }
    tree.init(n);
}

int minimum_jumps(int A, int B, int C, int D) {
    int mx = tree.query2(C, D+1);
    int cur2 = B, cur3 = -1;
    for (int j=19;j>=0;j--) if (cur2-(1<<j)+1>=A && max(sp1[cur2][j], cur3)<mx){
        cur3 = max(sp1[cur2][j], cur3);
        cur2 -= (1<<j);
    }
    A = cur2+1;
    int tmp = tree.query(A, B+1, mx);
    if (tmp==-1) return -1;

    int cur = INV[tmp], ans = 0;
    /*cur2 = C, cur3 = -1;
    for (int j=19;j>=0;j--) if (cur2+(1<<j)-1<=D && max(sp2[cur2][j], cur3)<a[cur]){
        cur3 = max(sp2[cur2][j], cur3);
        cur2 += (1<<j);
    }
    C = cur2;*/

    /*for (int j=19;j>=0;j--) if (sp3[cur][j]!=-1 && a[sp3[cur][j]]<mx && sp3[cur][j]<C) cur = sp3[cur][j], ans += (1<<j);
    for (int j=19;j>=0;j--) if (sp4[cur][j]!=n && a[sp4[cur][j]]<mx && sp4[cur][j]<C) cur = sp4[cur][j], ans += (1<<j);
    if (cur==-1 || cur==n) return -1;
    cur = sp4[cur][0], ans++;
    if (cur<C || cur>D) return -1;*/

    int ret = 1e9, tmp3 = 0;
    while(cur!=-1 && a[cur]<=mx){
        cur2 = cur, ans = tmp3;
        for (int j=19;j>=0;j--) if (sp4[cur2][j]!=n && a[sp4[cur2][j]]<mx && sp4[cur2][j]<C) cur2 = sp4[cur2][j], ans += (1<<j);
        if (cur2==-1 || cur2==n){
            cur = sp3[cur][0];
            tmp3++;
            continue;
        }
        cur2 = sp4[cur2][0], ans++;
        if (cur2<C || cur2>D){
            cur = sp3[cur][0];
            tmp3++;
            continue;
        }
        ret = min(ret, ans);

        cur = sp3[cur][0];
        tmp3++;
    }
    if (ret==1e9) return -1;
    return ret;
}

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