제출 #904020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
904020		efedmrlr	밀림 점프 (APIO21_jumps)	C++17	48 / 100	1791 ms	140852 KiB

jumps

#include "jumps.h"

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e7 + 5;
const int ALPH = 26;
const int LGN = 25;
const int MAXN = 2e5+5;
constexpr int MOD = 1e9+7;
int n,m,q;
vector<int> h(MAXN), revh(MAXN);
vector<int> low[LGN], high[LGN];
vector<array<int,2> > adj(MAXN, array<int,2>({0,0}));

struct SegT {
    vector<vector<int> > data;
    int sz;
    SegT() {}
    void build(int tl, int tr, int v, vector<int> &vec) {
        if(tl == tr) {
            data[v].pb(vec[tl]);
            return;
        }
        int tm = (tl + tr) >> 1;
        build(tl, tm, v<<1, vec);
        build(tm + 1, tr, v<<1^1, vec);
        // data[v].resize(data[v<<1].size() + data[v<<1^1].size());
        merge(all(data[v<<1]), all(data[v<<1^1]), back_inserter(data[v]));
    }
    void reset(int s, vector<int> &vec) {
        sz = s;
        data.assign(4*(sz + 3), vector<int>());
        build(0, sz, 1, vec);
    }
    int getMax(int tl, int tr, int v, int l, int r, int x) {
        if(tl >= l && tr <= r) {
            auto itr = upper_bound(all(data[v]), x) - data[v].begin();
            if(itr > 0) {
                itr--;
                return data[v][itr];
            }
            return -INF;
        }
        if(tl > r || tr < l) {
            return -INF;
        }
        int tm = (tl + tr) >> 1;
        return max(getMax(tl, tm, v<<1, l, r, x), getMax(tm + 1, tr, v<<1^1, l, r, x));
    } 
    int getMax(int l, int r, int x) {
        l = max(0, l); r = min(sz, r);
        if(l > r) return -INF;
        return getMax(0, sz, 1, l, r, x);
    }
    int getMin(int tl, int tr, int v, int l, int r, int x) {
        if(tl >= l && tr <= r) {
            auto itr = upper_bound(all(data[v]), x) - data[v].begin();
            if(itr < data[v].size()) {
                return data[v][itr];
            }
            return INF;
        }
        if(tl > r || tr < l) {
            return INF;
        }
        int tm = (tl + tr) >> 1;
        return min(getMin(tl, tm, v<<1, l, r, x), getMin(tm + 1, tr, v<<1^1, l, r, x));
    } 
    int getMin(int l, int r, int x) {
        l = max(0, l); r = min(sz, r);
        if(l > r) return INF;
        return getMin(0, sz, 1, l, r, x);
    }
};

SegT seg, segr;
void init(int N, std::vector<int> H) {
    h[0] = 0;
    n = N;
    for(int i = 1 ;i<=n; i++) {
        h[i] = H[i - 1];
    }
    for(int i = 0; i<=n; i++) {
        revh[h[i]] = i;
    }
    set<int> st;
    vector<array<int,2> > srt(n);
    seg.reset(n, h);
    segr.reset(n, revh);
    for(int i = 1; i<=n; i++) {
        srt[i - 1] = {h[i], i};
        st.insert(i);
    }    
    sort(srt.begin(), srt.end());
    for(auto c : srt) {
        st.erase(c[1]);
        auto itr = st.lower_bound(c[1]);
        if(st.empty()) break;
        if(itr != st.end()) {
            adj[c[1]][1] = *itr;
        }
        if(itr != st.begin()) {
            itr--;
            adj[c[1]][0] = *itr;
        }
        if(h[adj[c[1]][0]] > h[adj[c[1]][1]]) {
            swap(adj[c[1]][0], adj[c[1]][1]);
        }
    }
    REP(i, LGN) {
        low[i].assign(n + 1, 0);
        high[i].assign(n + 1, 0);
    }
    for(int i = 1; i<=n; i++) {
        low[0][i] = adj[i][0];
        high[0][i] = adj[i][1];
    }
    for(int k = 1; k<LGN; k++) {
        for(int i = 1; i <= n; i++) {
            low[k][i] = low[k - 1][low[k - 1][i]];
            high[k][i] = high[k - 1][high[k - 1][i]];
        }
    }


}

int solve(int A, int C) {
    if(h[A] > h[C]) return -1;
    int ans = 0;
    for(int i = LGN - 1; i>=0; i--) {
        if(h[high[i][A]] && h[high[i][A]] <= h[C]) {
            A = high[i][A];
            ans += 1<<i;
        }
    }
    for(int i = LGN - 1; i>=0; i--) {
        if(h[low[i][A]] && h[low[i][A]] <= h[C]) {
            A = low[i][A];
            ans += 1<<i;
        }
    }
    // cout<<"ans:"<<ans<<" A:"<<A<<" C:"<<C<<"\n";
    if(A == C) return ans;
    return -1;
    
}

int minimum_jumps(int A, int B, int C, int D) {
    A++; B++; C++; D++;
    int cmax = seg.getMax(C, D, INF);
    cmax = revh[cmax];
    int left = segr.getMax(h[cmax], n, B);
    int fir = seg.getMax(max(left + 1, A), B, h[cmax]);
    if(fir < 1) return -1;
    fir = revh[fir];
    int mn = max(h[fir], seg.getMax(B + 1, C - 1, INF));
    int sec = segr.getMin(mn + 1, n, C - 1);
    if(sec > D) return -1;
    
    return solve(fir, sec);
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In member function 'int SegT::getMin(int, int, int, int, int, int)':
jumps.cpp:77:20: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             if(itr < data[v].size()) {
      |                ~~~~^~~~~~~~~~~~~~~~

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