oj.uz

Submission #569783

# Submission time Handle Problem Language Result Execution time Memory
569783 2022-05-27T19:16:46 Z Lobo Rainforest Jumps (APIO21_jumps) C++17
23 / 100
 1133 ms 67180 KB 
#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, h[maxn], nx[maxn][25], nxl[maxn][25], nxr[maxn][25];

pair<int,int> tr[4*maxn];

void att(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    if(l == r) {
        tr[no] = mp(val,l);
        return;
    }
    int f1 = 2*no;
    int f2 = 2*no+1;
    int mid = (l+r)/2;
    att(f1,l,mid,pos,val);
    att(f2,mid+1,r,pos,val);
    tr[no] = max(tr[f1],tr[f2]);
}

pair<int,int> qrrmx(int no, int l, int r, int L, int R) {
    if(l > R || r < L) return mp(0,0);
    if(l >= L && r <= R) return tr[no];
    int f1 = 2*no;
    int f2 = 2*no+1;
    int mid = (l+r)/2;
    return max(qrrmx(f1,l,mid,L,R),qrrmx(f2,mid+1,r,L,R));
}

void init(int N, vector<int> H) {
    n = N;

    for(int i = 1; i <= n; i++) {
        h[i] = H[i-1];
        att(1,1,n,i,h[i]);
    }
    //os proximos da esquerda e direita de cada um e 0 se não tiver
    stack<pair<int,int>> stl;
    for(int i = 1; i <= n; i++) {
        while(stl.size() && stl.top().fr < h[i]) {
            stl.pop();
        }

        if(stl.size()) nxl[i][0] = stl.top().sc;
        else nxl[i][0] = 0;

        stl.push(mp(h[i],i));
    }
    stack<pair<int,int>> str;
    for(int i = n; i >= 1; i--) {
        while(str.size() && str.top().fr < h[i]) {
            str.pop();
        }

        if(str.size()) nxr[i][0] = str.top().sc;
        else nxr[i][0] = 0;

        str.push(mp(h[i],i));
    }

    //sei qual o proximo normal de cada um
    for(int i = 1; i <= n; i++) {
        if(nxr[i][0] == 0 || h[nxl[i][0]] > h[nxr[i][0]]) nx[i][0] = nxl[i][0];
        else nx[i][0] = nxr[i][0];

        // cout << i << " " << nx[i][0] << " " << nxl[i][0] << " " << nxr[i][0] << endl;
    }

    for(int pt = 1; pt <= 20; pt++) {
        for(int i = 1; i <= n; i++) {
            nx[i][pt] = nx[nx[i][pt-1]][pt-1];
        }
    }
    for(int pt = 1; pt <= 20; pt++) {
        for(int i = 1; i <= n; i++) {
            nxl[i][pt] = nxl[nxl[i][pt-1]][pt-1];
        }
    }
    for(int pt = 1; pt <= 20; pt++) {
        for(int i = 1; i <= n; i++) {
            nxr[i][pt] = nxr[nxr[i][pt-1]][pt-1];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    A++;
    B++;
    C++;
    D++;
    //ir do a para o c

    //pego o maior cara entre a e b < c
    //na vez do h[c] qual era o maior do intervalo
    
    int s = 0;
    int l = A;
    int r = B;
    while(l <= r) {
        int mid = (l+r)/2;
        // cout << mid << " " << qrrmx(1,1,n,mid,B).fr << endl;
        if(qrrmx(1,1,n,mid,B).fr < h[C]) {
            s = mid;
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    if(s == 0) return -1;
    int t = C;
    int ans = 0;
    for(int pt = 20; pt >= 0; pt--) {
        if(nx[s][pt] == 0 || h[nx[s][pt]] > h[t]) continue;
        ans+= (1<<pt);
        s = nx[s][pt];
    }

    //vai so para a direita ate chegar no t
    for(int pt = 20; pt >= 0; pt--) {
        if(nxr[s][pt] == 0 || nxr[s][pt] > t) continue;
        ans+= (1<<pt);
        s = nxr[s][pt];
    }

    if(s == t) return ans;
    else return -1;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 274 ms 30232 KB Output is correct
5 Correct 841 ms 65352 KB Output is correct
6 Correct 636 ms 11384 KB Output is correct
7 Correct 977 ms 65468 KB Output is correct
8 Correct 552 ms 23320 KB Output is correct
9 Correct 998 ms 65352 KB Output is correct
10 Correct 1133 ms 67092 KB Output is correct
11 Correct 1086 ms 66860 KB Output is correct
12 Correct 974 ms 66884 KB Output is correct
13 Correct 938 ms 65340 KB Output is correct
14 Correct 929 ms 66236 KB Output is correct
15 Correct 1049 ms 67108 KB Output is correct
16 Correct 834 ms 66992 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 3 ms 392 KB Output is correct
21 Correct 3 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 15 ms 848 KB Output is correct
28 Correct 23 ms 976 KB Output is correct
29 Correct 19 ms 848 KB Output is correct
30 Correct 18 ms 976 KB Output is correct
31 Correct 18 ms 976 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 115 ms 37604 KB Output is correct
34 Correct 195 ms 65460 KB Output is correct
35 Correct 180 ms 66872 KB Output is correct
36 Correct 176 ms 65440 KB Output is correct
37 Correct 184 ms 66248 KB Output is correct
38 Correct 214 ms 67108 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 274 ms 30232 KB Output is correct
5 Correct 841 ms 65352 KB Output is correct
6 Correct 636 ms 11384 KB Output is correct
7 Correct 977 ms 65468 KB Output is correct
8 Correct 552 ms 23320 KB Output is correct
9 Correct 998 ms 65352 KB Output is correct
10 Correct 1133 ms 67092 KB Output is correct
11 Correct 1086 ms 66860 KB Output is correct
12 Correct 974 ms 66884 KB Output is correct
13 Correct 938 ms 65340 KB Output is correct
14 Correct 929 ms 66236 KB Output is correct
15 Correct 1049 ms 67108 KB Output is correct
16 Correct 834 ms 66992 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 3 ms 392 KB Output is correct
21 Correct 3 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 15 ms 848 KB Output is correct
28 Correct 23 ms 976 KB Output is correct
29 Correct 19 ms 848 KB Output is correct
30 Correct 18 ms 976 KB Output is correct
31 Correct 18 ms 976 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 115 ms 37604 KB Output is correct
34 Correct 195 ms 65460 KB Output is correct
35 Correct 180 ms 66872 KB Output is correct
36 Correct 176 ms 65440 KB Output is correct
37 Correct 184 ms 66248 KB Output is correct
38 Correct 214 ms 67108 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 0 ms 336 KB Output is correct
41 Correct 0 ms 208 KB Output is correct
42 Correct 304 ms 30304 KB Output is correct
43 Correct 1065 ms 65472 KB Output is correct
44 Correct 475 ms 11336 KB Output is correct
45 Correct 1096 ms 65456 KB Output is correct
46 Correct 521 ms 23368 KB Output is correct
47 Correct 847 ms 65460 KB Output is correct
48 Correct 996 ms 67180 KB Output is correct
49 Correct 1093 ms 66876 KB Output is correct
50 Correct 1072 ms 66780 KB Output is correct
51 Correct 924 ms 65464 KB Output is correct
52 Correct 1006 ms 66304 KB Output is correct
53 Correct 923 ms 66984 KB Output is correct
54 Correct 944 ms 67112 KB Output is correct
55 Correct 0 ms 336 KB Output is correct
56 Incorrect 263 ms 65224 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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