oj.uz

Submission #569778

# Submission time Handle Problem Language Result Execution time Memory
569778 2022-05-27T18:44:04 Z Lobo Rainforest Jumps (APIO21_jumps) C++17
27 / 100
 1312 ms 123920 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[22*maxn];
int f1[22*maxn], f2[22*maxn], bg[maxn], cnt = 0;
int att(int no, int l, int r, int no1, int pos, int val) {
    if(no == 0) no = ++cnt;
    if(l > pos || r < pos) return no;
    if(l == r) {
        tr[no] = mp(val,l);
        return no;
    }

    int mid = (l+r)/2;
    if(pos <= mid) {
        //vai para esquerda
        f1[no] = att(f1[no],l,mid,f1[no1],pos,val);
        f2[no] = f2[no1];
    }
    else {
        f2[no] = att(f2[no],mid+1,r,f2[no1],pos,val);
        f1[no] = f1[no1];
    }
    tr[no] = max(tr[f1[no]],tr[f2[no]]);
    return no;
}

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 mid = (l+r)/2;
    return max(qrrmx(f1[no],l,mid,L,R),qrrmx(f2[no],mid+1,r,L,R));
}

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

    vector<pair<int,int>> vec;
    for(int i = 1; i <= n; i++) {
        h[i] = H[i-1];
        vec.pb(mp(h[i],i));
    }
    sort(all(vec));
    int ant = 0;
    for(auto X : vec) {
        ant = att(0,1,n,ant,X.sc,X.fr);
        bg[X.fr] = ant;
    }
    // cout << cnt << endl;

    //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 = qrrmx(bg[h[C]],1,n,A,B).sc;
    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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 330 ms 97808 KB Output is correct
4 Correct 1119 ms 123840 KB Output is correct
5 Correct 958 ms 60952 KB Output is correct
6 Correct 1104 ms 123792 KB Output is correct
7 Correct 1063 ms 83344 KB Output is correct
8 Correct 1277 ms 123920 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 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 336 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 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 319 ms 54484 KB Output is correct
5 Correct 1167 ms 122256 KB Output is correct
6 Correct 676 ms 19048 KB Output is correct
7 Correct 1226 ms 122396 KB Output is correct
8 Correct 664 ms 40636 KB Output is correct
9 Correct 1302 ms 122296 KB Output is correct
10 Correct 1233 ms 123856 KB Output is correct
11 Correct 1152 ms 123736 KB Output is correct
12 Correct 1230 ms 123588 KB Output is correct
13 Correct 1267 ms 122296 KB Output is correct
14 Correct 1243 ms 123172 KB Output is correct
15 Correct 962 ms 123828 KB Output is correct
16 Correct 1052 ms 123772 KB Output is correct
17 Correct 0 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 3 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 720 KB Output is correct
27 Correct 18 ms 1360 KB Output is correct
28 Correct 18 ms 1360 KB Output is correct
29 Correct 16 ms 1360 KB Output is correct
30 Correct 22 ms 1360 KB Output is correct
31 Correct 24 ms 1360 KB Output is correct
32 Correct 0 ms 336 KB Output is correct
33 Correct 152 ms 69528 KB Output is correct
34 Correct 285 ms 122308 KB Output is correct
35 Correct 210 ms 123552 KB Output is correct
36 Correct 269 ms 122244 KB Output is correct
37 Correct 234 ms 123024 KB Output is correct
38 Correct 235 ms 123888 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 319 ms 54484 KB Output is correct
5 Correct 1167 ms 122256 KB Output is correct
6 Correct 676 ms 19048 KB Output is correct
7 Correct 1226 ms 122396 KB Output is correct
8 Correct 664 ms 40636 KB Output is correct
9 Correct 1302 ms 122296 KB Output is correct
10 Correct 1233 ms 123856 KB Output is correct
11 Correct 1152 ms 123736 KB Output is correct
12 Correct 1230 ms 123588 KB Output is correct
13 Correct 1267 ms 122296 KB Output is correct
14 Correct 1243 ms 123172 KB Output is correct
15 Correct 962 ms 123828 KB Output is correct
16 Correct 1052 ms 123772 KB Output is correct
17 Correct 0 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 3 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 720 KB Output is correct
27 Correct 18 ms 1360 KB Output is correct
28 Correct 18 ms 1360 KB Output is correct
29 Correct 16 ms 1360 KB Output is correct
30 Correct 22 ms 1360 KB Output is correct
31 Correct 24 ms 1360 KB Output is correct
32 Correct 0 ms 336 KB Output is correct
33 Correct 152 ms 69528 KB Output is correct
34 Correct 285 ms 122308 KB Output is correct
35 Correct 210 ms 123552 KB Output is correct
36 Correct 269 ms 122244 KB Output is correct
37 Correct 234 ms 123024 KB Output is correct
38 Correct 235 ms 123888 KB Output is correct
39 Correct 0 ms 336 KB Output is correct
40 Correct 0 ms 336 KB Output is correct
41 Correct 0 ms 336 KB Output is correct
42 Correct 336 ms 54564 KB Output is correct
43 Correct 1148 ms 122280 KB Output is correct
44 Correct 698 ms 19152 KB Output is correct
45 Correct 1309 ms 122252 KB Output is correct
46 Correct 608 ms 40728 KB Output is correct
47 Correct 1230 ms 122284 KB Output is correct
48 Correct 1162 ms 123804 KB Output is correct
49 Correct 1312 ms 123688 KB Output is correct
50 Correct 1229 ms 123648 KB Output is correct
51 Correct 1196 ms 122416 KB Output is correct
52 Correct 1185 ms 123080 KB Output is correct
53 Correct 1040 ms 123800 KB Output is correct
54 Correct 947 ms 123804 KB Output is correct
55 Correct 0 ms 336 KB Output is correct
56 Incorrect 367 ms 121816 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 330 ms 97808 KB Output is correct
4 Correct 1119 ms 123840 KB Output is correct
5 Correct 958 ms 60952 KB Output is correct
6 Correct 1104 ms 123792 KB Output is correct
7 Correct 1063 ms 83344 KB Output is correct
8 Correct 1277 ms 123920 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -