oj.uz

답안 #497759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
497759 2021-12-23T18:02:54 Z Karliver 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1267 ms 50352 KB 
    
#include <bits/stdc++.h>
#include "jumps.h"
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
#define ff first
#define se second
#define mp make_pair
using ll = long long;
int mod = (ll)1e9 + 7;
const int INF = 1e9 + 1;

const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}

const int mxn = 2e5+2;


const int G = 20;
int F[mxn][G], L[mxn][G], R[mxn][G];

V<int> H;

int n;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)

void init(int N, V<int> a) {
    
    H = a;
    H.insert(H.begin(), INF);
    H.push_back(INF);
    //debug(H);
    n = N;
    stack<int> st;
    forn(i, N+2) {
        while(sz(st) && H[st.top()] <= H[i])
            st.pop();
        
        L[i][0] = sz(st) ? st.top() : i;
        st.push(i);
    }
    while(sz(st))st.pop();
    rforn(i, N+2) {
        while(sz(st) && H[st.top()] <= H[i])
            st.pop();
        
        R[i][0] = sz(st) ? st.top() : i;
        st.push(i);
    }
    
    forn(i,N+2) F[i][0] = (H[L[i][0]] < H[R[i][0]] ? R[i][0] : L[i][0]);

    for(int j = 1;j < G;++j) forn(i,N+2) {
        L[i][j] = L[L[i][j-1]][j-1];
        R[i][j] = R[R[i][j-1]][j-1];
        F[i][j] = F[F[i][j-1]][j-1];
    }


}


int minimum_jumps(int A, int B, int C, int D) {
    ++A, ++B, ++C, ++D;
    if(B + 1 == C) {
        return R[B][0] <= D ? 1 : -1;
    }
    int md = B + 1;
    // md is biggest element in (B,C)
    // we have to cross through md eventually
    rforn(i, G) if(R[md][i] < C)md = R[md][i];
    if(H[B] > H[md])
        return R[md][0] <= D ? 1 : -1;
    int go = B;
    // the optimal is where the H[index] in greatest integer < H[mid] in range [A, B]
    // go is where we start from

    rforn(i, G) if(L[go][i] >= A && H[L[go][i]] < H[md]) go = L[go][i];
    int ret = 0;
    if(L[go][0] >= A) {
        if(R[L[go][0]][0] <= D)return 1;
    }
    else {
        rforn(i, G) if(H[F[go][i]] <= H[md]) {
            go = F[go][i];
            ret += 1 << i;
        }

        if(go == md)return R[go][md] <= D ? ret+1 : -1;
        else if(L[go][0] && R[L[go][0]][0] <= D)return ret+2;
    }

    rforn(i, G) if(R[go][i] < C) {
        ret += 1 << i;
        go = R[go][i];
    }
    go = R[go][0];

    if(C <= go && go <= D)return ret+1;
    else return -1;

}
/*
int main() {

    init(7, {3, 2, 1, 6, 4, 5, 7});
    cout << minimum_jumps(3, 4, 6, 6) << '\n';
}*/

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 209 ms 40216 KB Output is correct
4 Correct 1267 ms 50316 KB Output is correct
5 Correct 1069 ms 25524 KB Output is correct
6 Correct 1045 ms 50352 KB Output is correct
7 Correct 1018 ms 34568 KB Output is correct
8 Correct 1188 ms 50312 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Incorrect 2 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Incorrect 2 ms 200 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 97 ms 39972 KB Output is correct
6 Correct 134 ms 49548 KB Output is correct
7 Correct 53 ms 25476 KB Output is correct
8 Correct 106 ms 49580 KB Output is correct
9 Correct 13 ms 7752 KB Output is correct
10 Correct 105 ms 49548 KB Output is correct
11 Correct 101 ms 50344 KB Output is correct
12 Correct 105 ms 50192 KB Output is correct
13 Correct 100 ms 50088 KB Output is correct
14 Incorrect 104 ms 49700 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 281 ms 22820 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 281 ms 22820 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 209 ms 40216 KB Output is correct
4 Correct 1267 ms 50316 KB Output is correct
5 Correct 1069 ms 25524 KB Output is correct
6 Correct 1045 ms 50352 KB Output is correct
7 Correct 1018 ms 34568 KB Output is correct
8 Correct 1188 ms 50312 KB Output is correct
9 Correct 0 ms 200 KB Output is correct
10 Correct 0 ms 200 KB Output is correct
11 Correct 0 ms 200 KB Output is correct
12 Correct 0 ms 200 KB Output is correct
13 Incorrect 2 ms 200 KB Output isn't correct
14 Halted 0 ms 0 KB -