oj.uz

Submission #668325

# Submission time Handle Problem Language Result Execution time Memory
668325 2022-12-03T16:13:35 Z Minhho Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1049 ms 34876 KB 
#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], seg[2*maxn], hi[20][maxn], l[20][maxn], r[20][maxn], n, q;

inline int qry(int lx, int rx)
{
    int ans = 0;
    for (lx+=n, rx+=n+1; lx<rx; lx>>=1, rx>>=1)
    {
        if (lx & 1) ans = max(ans, seg[lx++]);
        if (rx & 1) ans = max(ans, seg[--rx]);
    }
    return ans;
}

void init(int N, vector<int> H)
{
    n = N;
    for (int i=1; i<=n; i++) a[i] = H[i-1], seg[n+i] = a[i];
    for (int i=n; i>=1; i--) seg[i] = max(seg[i<<1], seg[i<<1|1]);
    vector<int> dq;
    for (int i=n; i>=1; i--)
    {
        while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
        r[0][i] = dq.size() ? dq.back() : -1;
        dq.emplace_back(i);
    }
    dq.clear();
    for (int i=1; i<=n; i++)
    {
        while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
        l[0][i] = dq.size() ? dq.back() : -1;
        dq.emplace_back(i);
    }
//    for (int i=1; i<=n; i++) hi[0][i] = (r[0][i] != -1 && (l[0][i] == -1 || a[r[0][i]] >= a[l[0][i]]) ? r[0][i] : l[0][i]);
//    for (int i=1; i<=n; i++) cerr<<i<<" "<<l[0][i]<<" "<<r[0][i]<<"\n";
    for (int i=1; i<=18; i++)
        for (int j=1; j<=n; j++)
            r[i][j] = (r[i-1][j] != -1 ? r[i-1][r[i-1][j]] : -1),
            l[i][j] = (l[i-1][j] != -1 ? l[i-1][l[i-1][j]] : -1);//, cerr<<"SPT: "<<i<<" "<<j<<" "<<r[i][j]<<"\n";
//            hi[i][j] = hi[i-1][hi[i-1][j]];
}

int minimum_jumps(int A, int B, int C, int D)
{
    int ls, rs, le, re;
//    cin>>ls>>rs>>le>>re;
    ls = A, rs = B, le = C, re = D;
    ls++, rs++, le++, re++;
    if (qry(rs, le-1) > qry(le, re)) return -1;
    int cur = rs, mx = qry(le, re), ans = 0;
    for (int i=18; i>=0; i--)
        if (l[i][cur] != -1 && l[i][cur] >= ls && a[l[i][cur]] < mx) cur = l[i][cur];
    for (int i=18; i>=0; i--)
        if (r[i][cur] != -1 && r[i][cur] < le) ans += (1<<i), cur = r[i][cur];
    return ans + 1;
}

//int main()
//{
//
//}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 109 ms 27920 KB Output is correct
4 Correct 1049 ms 34848 KB Output is correct
5 Correct 914 ms 17960 KB Output is correct
6 Correct 981 ms 34876 KB Output is correct
7 Correct 766 ms 24124 KB Output is correct
8 Correct 913 ms 34752 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Incorrect 2 ms 464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Incorrect 2 ms 464 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 32 ms 27540 KB Output is correct
6 Correct 40 ms 33952 KB Output is correct
7 Correct 20 ms 17604 KB Output is correct
8 Correct 41 ms 33880 KB Output is correct
9 Correct 6 ms 5584 KB Output is correct
10 Correct 41 ms 33960 KB Output is correct
11 Correct 34 ms 34864 KB Output is correct
12 Correct 33 ms 34584 KB Output is correct
13 Incorrect 34 ms 34620 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 109 ms 27920 KB Output is correct
4 Correct 1049 ms 34848 KB Output is correct
5 Correct 914 ms 17960 KB Output is correct
6 Correct 981 ms 34876 KB Output is correct
7 Correct 766 ms 24124 KB Output is correct
8 Correct 913 ms 34752 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 0 ms 464 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 2 ms 464 KB Output is correct
14 Incorrect 2 ms 464 KB Output isn't correct
15 Halted 0 ms 0 KB -