oj.uz

Submission #413360

# Submission time Handle Problem Language Result Execution time Memory
413360 2021-05-28T14:41:28 Z mat_v Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 124 ms 80332 KB 
#include "jumps.h"
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))

using namespace std;

int n;
int niz[200005];
int levo[200005][20];
int desno[200005][20];
int pravi[200005][20];
int poz[200005];

void init(int N, std::vector<int> H) {
    n = N;
    ff(i,0,n - 1){
        niz[i + 1] = H[i];
        poz[niz[i + 1]] = i+1;
    }
    stack<int> s;
    ff(i,1,n){
        while(!s.empty() && niz[s.top()] < niz[i])s.pop();
        if(!s.empty())levo[i][0] = s.top();
        s.push(i);
    }
    while(!s.empty())s.pop();
    fb(i,n,1){
        while(!s.empty() && niz[s.top()] < niz[i])s.pop();
        if(!s.empty())desno[i][0] = s.top();
        s.push(i);
    }
    fb(i,n,1){
        ff(j,1,18)desno[i][j] = desno[desno[i][j - 1]][j - 1];
    }
    ff(i,1,n){
        ff(j,1,18)levo[i][j] = levo[levo[i][j - 1]][j - 1];
    }
    fb(i,n - 1,1){
        int sta = poz[i];
        int lv = levo[sta][0], rv = desno[sta][0];
        if(niz[lv] > niz[rv])pravi[sta][0] = lv;
        else pravi[sta][0] = rv;
        ff(j,1,18)pravi[sta][j] = pravi[pravi[sta][j - 1]][j - 1];
    }

}

int dist(int x, int y){
    if(niz[y] < niz[x])return -1;
    int ans = 0;
    int lv = x;
    int poc = y;
    fb(j,18,0){
        if(pravi[lv][j] && niz[pravi[lv][j]] < niz[poc]){
            ans += (1<<j);
            lv = pravi[lv][j];
        }
    }
    fb(j,18,0){
        if(desno[lv][j] && niz[desno[lv][j]] < niz[poc]){
            ans += (1<<j);
            lv = desno[lv][j];
        }
    }
    if(desno[lv][0] == poc)return ans+1;
    return -1;
}

int minimum_jumps(int A, int B, int C, int D) {
    A++;
    B++;
    C++;
    D++;
    int l1,r1,l2,r2;
    l1 = A, r1 = B, l2 = C, r2 = D;
    int tr = l2;
    fb(j,18,0){
        if(desno[tr][j] && desno[tr][j] <= r2)tr = desno[tr][j];
    }
    int val = niz[tr];

    int lv = r1;
    fb(j,18,0){
        if(levo[lv][j] && levo[lv][j] >= l1 && niz[levo[lv][j]] < val)lv = levo[lv][j];
    }
    if(niz[lv] > val)return -1;

    int ans = 1e9;

    ff(j,l2,r2){
        if(dist(lv,j) > 0)ans = min(ans, dist(lv,j));
    }
    if(ans == 1e9)return -1;

    int mks = 0;
    int idx = 0;
    if(r1 <= l2-1){
        idx = r1;
        fb(j,18,0){
            if(desno[idx][j] && desno[idx][j] <= l2-1)idx = desno[idx][j];
        }
        mks = niz[idx];
    }
    if(mks > val)return -1;
    if(mks <= niz[lv])return 1;
    int res = dist(lv, idx);
    assert(res >= ans);

    return res;
}
/*
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2

*/

Compilation message

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
jumps.cpp:17:5: note: in expansion of macro 'ff'
   17 |     ff(i,0,n - 1){
      |     ^~
jumps.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
jumps.cpp:22:5: note: in expansion of macro 'ff'
   22 |     ff(i,1,n){
      |     ^~
jumps.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
jumps.cpp:28:5: note: in expansion of macro 'fb'
   28 |     fb(i,n,1){
      |     ^~
jumps.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
jumps.cpp:33:5: note: in expansion of macro 'fb'
   33 |     fb(i,n,1){
      |     ^~
jumps.cpp:3:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
jumps.cpp:34:9: note: in expansion of macro 'ff'
   34 |         ff(j,1,18)desno[i][j] = desno[desno[i][j - 1]][j - 1];
      |         ^~
jumps.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
jumps.cpp:36:5: note: in expansion of macro 'ff'
   36 |     ff(i,1,n){
      |     ^~
jumps.cpp:3:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
jumps.cpp:37:9: note: in expansion of macro 'ff'
   37 |         ff(j,1,18)levo[i][j] = levo[levo[i][j - 1]][j - 1];
      |         ^~
jumps.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
jumps.cpp:39:5: note: in expansion of macro 'fb'
   39 |     fb(i,n - 1,1){
      |     ^~
jumps.cpp:3:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
jumps.cpp:44:9: note: in expansion of macro 'ff'
   44 |         ff(j,1,18)pravi[sta][j] = pravi[pravi[sta][j - 1]][j - 1];
      |         ^~
jumps.cpp: In function 'int dist(int, int)':
jumps.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
jumps.cpp:54:5: note: in expansion of macro 'fb'
   54 |     fb(j,18,0){
      |     ^~
jumps.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
jumps.cpp:60:5: note: in expansion of macro 'fb'
   60 |     fb(j,18,0){
      |     ^~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
jumps.cpp:78:5: note: in expansion of macro 'fb'
   78 |     fb(j,18,0){
      |     ^~
jumps.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
jumps.cpp:84:5: note: in expansion of macro 'fb'
   84 |     fb(j,18,0){
      |     ^~
jumps.cpp:3:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    3 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
jumps.cpp:91:5: note: in expansion of macro 'ff'
   91 |     ff(j,l2,r2){
      |     ^~
jumps.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
jumps.cpp:100:9: note: in expansion of macro 'fb'
  100 |         fb(j,18,0){
      |         ^~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Runtime error 123 ms 80332 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 512 KB Execution killed with signal 6
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 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Runtime error 124 ms 46164 KB Execution killed with signal 6
5 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 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Runtime error 124 ms 46164 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Runtime error 123 ms 80332 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -