oj.uz

Submission #414612

# Submission time Handle Problem Language Result Execution time Memory
414612 2021-05-30T18:08:58 Z tatyam Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 1253 ms 46256 KB 
#include <bits/stdc++.h>
using namespace std;
 
int N, lgN;
vector<vector<int>> rmq, low, high;

void init(int N, vector<int> H) {
    ::N = N;
    lgN = __lg(N);
    rmq.assign(lgN + 1, vector<int>(N));
    low.assign(lgN + 1, vector<int>(N, -1));
    high.assign(lgN + 1, vector<int>(N, -1));
    rmq[0] = H;
    for(int i = 0; i < lgN; i++) for(int j = 0; j + (2 << i) <= N; j++) rmq[i + 1][j] = max(rmq[i][j], rmq[i][j + (1 << i)]);
    vector<int> q;
    for(int i = 0; i < N; i++){
        while(q.size() && H[q.back()] < H[i]){
            const int j = q.back();
            q.pop_back();
            low[0][j] = i;
        }
        q.push_back(i);
    }
    for(int i = N; i--; ){
        while(q.size() && H[q.back()] < H[i]){
            const int j = q.back();
            q.pop_back();
            high[0][j] = i;
        }
        q.push_back(i);
    }
    for(int i = 0; i < N; i++) if(int &x = low[0][i], &y = high[0][i]; x != -1 && (y == -1 || H[x] > H[y])) swap(x, y);
    for(int i = 0; i < lgN; i++) for(int j = 0; j < N; j++) if(low[i][j] != -1) low[i + 1][j] = low[i][low[i][j]];
    for(int i = 0; i < lgN; i++) for(int j = 0; j < N; j++) if(high[i][j] != -1) high[i + 1][j] = high[i][high[i][j]];
}

int get(int l, int r){
    assert(0 <= l && l < r && r <= N);
    const int x = __lg(r - l);
    return max(rmq[x][l], rmq[x][r - (1 << x)]);
}
 
int minimum_jumps(int A, int B, int C, int D) {
    auto& H = rmq[0];
    const int X = get(B, C), Y = get(C, D + 1);
    if(X >= Y) return -1;
    {
        int a = B;
        for(int i = lgN; i >= 0; i--) if(const int a2 = a - (1 << i); a2 >= A && get(a2, B + 1) < Y) a = a2;
        A = a;
    }
    const int s = get(A, B + 1);
    if(s >= X) return 1;
    int ans = 2, at = A;
    for(int i = lgN; i >= 0; i--) if(const int at2 = at + (1 << i); at2 < B + 1 && get(at2, B + 1) >= s) at = at2;
    for(int i = lgN; i--; ) if(high[i][at] != -1 && H[high[i][at]] < X){
        ans += 1 << i;
        at = high[i][at];
    }
    if(high[0][at] != -1 && H[high[0][at]] < Y) return ans;
    for(int i = lgN; i--; ) if(low[i][at] != -1 && H[low[i][at]] < X){
        ans += 1 << i;
        at = low[i][at];
    }
    return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Incorrect 202 ms 36880 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Correct 3 ms 200 KB Output is correct
7 Correct 3 ms 200 KB Output is correct
8 Correct 4 ms 200 KB Output is correct
9 Correct 2 ms 200 KB Output is correct
10 Correct 5 ms 200 KB Output is correct
11 Incorrect 4 ms 200 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 3 ms 200 KB Output is correct
6 Correct 3 ms 200 KB Output is correct
7 Correct 3 ms 200 KB Output is correct
8 Correct 4 ms 200 KB Output is correct
9 Correct 2 ms 200 KB Output is correct
10 Correct 5 ms 200 KB Output is correct
11 Incorrect 4 ms 200 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 66 ms 36240 KB Output is correct
6 Correct 71 ms 44956 KB Output is correct
7 Correct 34 ms 21852 KB Output is correct
8 Correct 69 ms 44848 KB Output is correct
9 Correct 10 ms 5832 KB Output is correct
10 Correct 69 ms 44928 KB Output is correct
11 Incorrect 65 ms 46256 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 321 ms 19600 KB Output is correct
5 Correct 1134 ms 44848 KB Output is correct
6 Correct 768 ms 6852 KB Output is correct
7 Correct 1167 ms 44848 KB Output is correct
8 Correct 725 ms 14780 KB Output is correct
9 Correct 1130 ms 44932 KB Output is correct
10 Incorrect 1253 ms 46196 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 321 ms 19600 KB Output is correct
5 Correct 1134 ms 44848 KB Output is correct
6 Correct 768 ms 6852 KB Output is correct
7 Correct 1167 ms 44848 KB Output is correct
8 Correct 725 ms 14780 KB Output is correct
9 Correct 1130 ms 44932 KB Output is correct
10 Incorrect 1253 ms 46196 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Incorrect 202 ms 36880 KB Output isn't correct
4 Halted 0 ms 0 KB -