oj.uz

Submission #984458

# Submission time Handle Problem Language Result Execution time Memory
984458 2024-05-16T17:02:52 Z shjeong Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1076 ms 109244 KB 
#include "jumps.h"
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
vector<ll> v;
ll n;
ll L[202020][22];
ll R[202020][22];
ll M[202020][22];
void init(int N, std::vector<int> H) {
  assert(N!=200);
    n=N;
    v.resize(n+1,0);
    for(int i = 1 ; i <= n ; i++)v[i] = H[i-1];
    stack<ll> st;
    for(int i = 1 ; i <= n ; i++){
        while(st.size() and v[st.top()] < v[i]){
            M[st.top()][0] = R[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }
    while(st.size())st.pop();
    for(int i = n ; i >= 1 ; i--){
        while(st.size() and v[st.top()] < v[i]){
            L[st.top()][0] = i;
            M[st.top()][0] = (v[i] > v[R[st.top()][0]] ? i : R[st.top()][0]);
            st.pop();
        }
        st.push(i);
    }
    for(int j = 1 ; j <= 20 ; j++){
        for(int i = 1 ; i <= n ; i++){
            L[i][j] = L[L[i][j-1]][j-1];
            R[i][j] = R[R[i][j-1]][j-1];
            M[i][j] = M[M[i][j-1]][j-1];
        }
    }
}
 
ll RMQ(ll l, ll r){
    ll ret = l;
    for(int i = 20 ; i >= 0 ; i--){
        if(R[ret][i]>0 and R[ret][i]<=r)ret = R[ret][i];
    }
    return v[ret];
}
int minimum_jumps(int A, int B, int C, int D) {
    A++; B++; C++; D++;
    ll H = RMQ(B,C-1);
    ll mx = RMQ(C,D);
    ll cur = B;
    for(int i = 20 ; i >= 0 ; i--){
        if(L[cur][i]>0 and L[cur][i]>=A and v[L[cur][i]]<=mx)cur = L[cur][i];
    }
    ll ret = 0;
    for(int i = 20 ; i >= 0 ; i--){
        if(M[cur][i]>0 and v[M[cur][i]]<=H)cur = M[cur][i], ret += (1<<i);
    }
    bool flag = 0;
    ll x = ret+1;
    if(v[cur] == H)flag = 1;
    else if(0<M[cur][0] and v[M[cur][0]]<mx){
        cur = M[cur][0], ret++;
    }
    for(int i = 20 ; i >= 0 ; i--){
        if(R[cur][i]>0 and R[cur][i]<C)cur = R[cur][i], ret += (1<<i);
    }
    if(cur<C)cur = R[cur][0], ret++;
    if(flag)assert(x==ret);
    return C <= cur and cur <= D ? ret : -1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 184 ms 91348 KB Output is correct
4 Correct 1046 ms 109004 KB Output is correct
5 Correct 865 ms 59216 KB Output is correct
6 Correct 953 ms 109228 KB Output is correct
7 Correct 798 ms 78680 KB Output is correct
8 Correct 1076 ms 109004 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 4440 KB Output is correct
6 Runtime error 3 ms 600 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 4440 KB Output is correct
6 Runtime error 3 ms 600 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 87 ms 93416 KB Output is correct
6 Correct 108 ms 107464 KB Output is correct
7 Correct 54 ms 61524 KB Output is correct
8 Correct 115 ms 107704 KB Output is correct
9 Correct 11 ms 23592 KB Output is correct
10 Correct 106 ms 107548 KB Output is correct
11 Correct 119 ms 108992 KB Output is correct
12 Correct 114 ms 109000 KB Output is correct
13 Correct 115 ms 108756 KB Output is correct
14 Correct 103 ms 107472 KB Output is correct
15 Correct 133 ms 108412 KB Output is correct
16 Correct 127 ms 108972 KB Output is correct
17 Correct 111 ms 109000 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 4564 KB Output is correct
20 Runtime error 3 ms 600 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2400 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 186 ms 55548 KB Output is correct
5 Correct 771 ms 107448 KB Output is correct
6 Correct 503 ms 23640 KB Output is correct
7 Correct 778 ms 107472 KB Output is correct
8 Correct 424 ms 42704 KB Output is correct
9 Correct 731 ms 107456 KB Output is correct
10 Correct 970 ms 109228 KB Output is correct
11 Correct 876 ms 109244 KB Output is correct
12 Correct 936 ms 108936 KB Output is correct
13 Correct 818 ms 107460 KB Output is correct
14 Correct 911 ms 108184 KB Output is correct
15 Correct 761 ms 109136 KB Output is correct
16 Correct 765 ms 109236 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Runtime error 3 ms 600 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2400 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 186 ms 55548 KB Output is correct
5 Correct 771 ms 107448 KB Output is correct
6 Correct 503 ms 23640 KB Output is correct
7 Correct 778 ms 107472 KB Output is correct
8 Correct 424 ms 42704 KB Output is correct
9 Correct 731 ms 107456 KB Output is correct
10 Correct 970 ms 109228 KB Output is correct
11 Correct 876 ms 109244 KB Output is correct
12 Correct 936 ms 108936 KB Output is correct
13 Correct 818 ms 107460 KB Output is correct
14 Correct 911 ms 108184 KB Output is correct
15 Correct 761 ms 109136 KB Output is correct
16 Correct 765 ms 109236 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Runtime error 3 ms 600 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 184 ms 91348 KB Output is correct
4 Correct 1046 ms 109004 KB Output is correct
5 Correct 865 ms 59216 KB Output is correct
6 Correct 953 ms 109228 KB Output is correct
7 Correct 798 ms 78680 KB Output is correct
8 Correct 1076 ms 109004 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 2 ms 4440 KB Output is correct
14 Runtime error 3 ms 600 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -