oj.uz

Submission #426065

# Submission time Handle Problem Language Result Execution time Memory
426065 2021-06-13T13:34:34 Z Ozy Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 21 ms 2968 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl

#define MAX 2000
#define izq first
#define der second

lli n,offset,grande,prim;
lli arr[MAX+2],st[4*MAX];
pair<lli,lli> lados[MAX+2];

lli busca(lli pos, lli l, lli r, lli ini, lli fin, lli val, lli tipo) {

    if (ini > fin) return -1;
    if (ini > r || fin < l) return -1;
    if (st[pos] < val) return -1;
    if (ini == fin) return ini;

    lli mitad = (ini+fin)/2;
    if (tipo == 1)  {
        lli a = busca(pos*2, l, r, ini, mitad, val, tipo);
        if (a == -1) return busca((pos*2)+1, l, r, mitad+1, fin, val, tipo);
        else return a;
    }
    else {
        lli a = busca((pos*2)+1, l, r, mitad+1, fin, val, tipo);
        if (a == -1) return busca(pos*2, l, r, ini, mitad, val, tipo);
        else return a;
    }

}

lli query(lli pos, lli l, lli r, lli ini, lli fin) {
    if (l > fin || r < ini) return -1;
    if (l <= ini && fin <= r) return st[pos];

    lli mitad=(ini+fin)/2;
    return max(query(pos*2, l,r, ini, mitad), query((pos*2)+1, l, r, mitad+1, fin));
}

void init(int N, std::vector<int> H) {

    n = N;
    rep(i,0,n-1) arr[i] = H[i];

    offset = 1;
    while (offset < n) offset *= 2;

    rep(i,0,n-1) st[offset+i] = arr[i];
    repa(i,offset-1,1) st[i] = max(st[i*2], st[(i*2)+1]);

    rep(i,0,n-1) {
        lados[i].izq = busca(1,0,i-1,0,offset-1,arr[i],0);
        lados[i].der = busca(1,i+1,offset-1,0,offset-1,arr[i],1);
    }
}

int minimum_jumps(int A, int B, int C, int D) {

    //grande = query(1,C,D,0,offset-1);
    //prim = busca(1,A,B, 0, offset-1, grande, 0);
    //if (prim == B)

    return C-A;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Runtime error 21 ms 2968 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Output isn't correct
2 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 Incorrect 1 ms 200 KB Output isn't correct
3 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 Incorrect 1 ms 200 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Runtime error 21 ms 2968 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -