oj.uz

Submission #668324

# Submission time Handle Problem Language Result Execution time Memory
668324 2022-12-03T16:12:20 Z Minhho Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1068 ms 34960 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 1 ms 464 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 143 ms 27932 KB Output is correct
4 Correct 973 ms 34848 KB Output is correct
5 Correct 672 ms 17856 KB Output is correct
6 Correct 798 ms 34884 KB Output is correct
7 Correct 822 ms 24092 KB Output is correct
8 Correct 1068 ms 34960 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 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 2 ms 464 KB Output is correct
6 Incorrect 3 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 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 2 ms 464 KB Output is correct
6 Incorrect 3 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 1 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 43 ms 27424 KB Output is correct
6 Correct 41 ms 33864 KB Output is correct
7 Correct 20 ms 17708 KB Output is correct
8 Correct 45 ms 33960 KB Output is correct
9 Correct 6 ms 5584 KB Output is correct
10 Correct 40 ms 33852 KB Output is correct
11 Correct 34 ms 34864 KB Output is correct
12 Correct 51 ms 34588 KB Output is correct
13 Incorrect 50 ms 34604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 187 ms 15788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 187 ms 15788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.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 143 ms 27932 KB Output is correct
4 Correct 973 ms 34848 KB Output is correct
5 Correct 672 ms 17856 KB Output is correct
6 Correct 798 ms 34884 KB Output is correct
7 Correct 822 ms 24092 KB Output is correct
8 Correct 1068 ms 34960 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 0 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 3 ms 464 KB Output isn't correct
15 Halted 0 ms 0 KB -