oj.uz

Submission #569656

# Submission time Handle Problem Language Result Execution time Memory
569656 2022-05-27T15:18:43 Z Turkhuu Rainforest Jumps (APIO21_jumps) C++17
39 / 100
 1352 ms 64632 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int L = 18;
const int inf = 1000000000;
int n;
vector<int> a;
vector<vector<int>> lo, hi, g;
bool subtask1 = true;
void init(int N, vector<int> H){
  n = N, a = H;
  g.resize(n);
  lo.assign(n, vector(L, -1));
  hi.assign(n, vector(L, -1));
  for(int i = 1; i < n; i++){
    if(a[i - 1] > a[i]){
      subtask1 = false;
    }
  }
  vector<int> idx(n);
  for(int i = 0; i < n; i++){
    idx[--a[i]] = i;
  }
  set<int> s;
  for(int i = n - 1; i >= 0; i--){
    auto j = s.lower_bound(idx[i]);
    int l = -1, r = -1;
    if(j != s.end()){
      r = a[*j];
      g[idx[i]].push_back(*j);
    }
    if(j != s.begin()){
      l = a[*prev(j)];
      g[idx[i]].push_back(*prev(j));
    }
    if(l != -1 && (r == -1 || l >= r)){
      lo[i][0] = r;
      hi[i][0] = l;
    } else{
      lo[i][0] = l;
      hi[i][0] = r;
    }
    s.insert(idx[i]);
  }
  for(int j = 1; j < L; j++){
    for(int i = 0; i < n; i++){
      if(lo[i][j - 1] != -1){
        lo[i][j] = lo[lo[i][j - 1]][j - 1];
      }
      if(hi[i][j - 1] != -1){
        hi[i][j] = hi[hi[i][j - 1]][j - 1];
      }
    }
  }
}
int minimum_jumps(int A, int B, int C, int D){
  if(subtask1){
    return C - B;
  }
  if(C == D){
    int H = -1;
    for(int i = A; i <= B; i++){
      if(a[i] < a[C]){
        H = max(H, a[i]);
      }
    }
    if(H == -1){
      return -1;
    }
    int G = a[C], c = 0;
    for(int i = L - 1; i >= 0; i--){
      if(hi[H][i] != -1 && hi[H][i] <= G){
        H = hi[H][i];
        c += 1 << i;
      }
    }
    for(int i = L - 1; i >= 0; i--){
      if(lo[H][i] != -1 && lo[H][i] <= G){
        H = lo[H][i];
        c += 1 << i;
      }
    }
    if(H != G){
      c = -1;
    }
    return c;
  }
  queue<int> q;
  vector<int> d(n, inf);
  for(int i = A; i <= B; i++){
    d[i] = 0;
    q.push(i);
  }
  while(!q.empty()){
    int i = q.front();
    q.pop();
    if(C <= i && i <= D){
      return d[i];
    }
    for(int j : g[i]){
      if(d[i] + 1 < d[j]){
        d[j] = d[i] + 1;
        q.push(j);
      }
    }
  }
  return -1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 211 ms 51372 KB Output is correct
4 Correct 969 ms 64524 KB Output is correct
5 Correct 735 ms 32500 KB Output is correct
6 Correct 895 ms 64388 KB Output is correct
7 Correct 663 ms 44104 KB Output is correct
8 Correct 946 ms 64456 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 251 ms 51936 KB Output is correct
6 Correct 334 ms 64412 KB Output is correct
7 Correct 119 ms 33088 KB Output is correct
8 Correct 322 ms 64540 KB Output is correct
9 Correct 28 ms 9928 KB Output is correct
10 Correct 325 ms 64424 KB Output is correct
11 Correct 168 ms 64400 KB Output is correct
12 Correct 177 ms 64408 KB Output is correct
13 Correct 171 ms 64436 KB Output is correct
14 Correct 270 ms 64484 KB Output is correct
15 Correct 216 ms 64416 KB Output is correct
16 Correct 190 ms 64472 KB Output is correct
17 Correct 198 ms 64484 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 0 ms 336 KB Output is correct
26 Correct 1 ms 592 KB Output is correct
27 Correct 2 ms 848 KB Output is correct
28 Correct 2 ms 940 KB Output is correct
29 Correct 2 ms 848 KB Output is correct
30 Correct 3 ms 848 KB Output is correct
31 Correct 2 ms 848 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 283 ms 64324 KB Output is correct
34 Correct 294 ms 64632 KB Output is correct
35 Correct 181 ms 64480 KB Output is correct
36 Correct 261 ms 64484 KB Output is correct
37 Correct 192 ms 64460 KB Output is correct
38 Correct 168 ms 64428 KB Output is correct
39 Correct 0 ms 208 KB Output is correct
40 Correct 141 ms 37448 KB Output is correct
41 Correct 285 ms 64428 KB Output is correct
42 Correct 163 ms 64408 KB Output is correct
43 Correct 235 ms 64380 KB Output is correct
44 Correct 189 ms 64488 KB Output is correct
45 Correct 185 ms 64488 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 282 ms 29704 KB Output is correct
5 Correct 1043 ms 64528 KB Output is correct
6 Correct 608 ms 10832 KB Output is correct
7 Correct 1122 ms 64556 KB Output is correct
8 Correct 556 ms 22364 KB Output is correct
9 Correct 1141 ms 64368 KB Output is correct
10 Correct 886 ms 64488 KB Output is correct
11 Correct 1081 ms 64432 KB Output is correct
12 Correct 1090 ms 64428 KB Output is correct
13 Correct 996 ms 64480 KB Output is correct
14 Correct 1066 ms 64548 KB Output is correct
15 Correct 900 ms 64484 KB Output is correct
16 Correct 886 ms 64492 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 2 ms 208 KB Output is correct
20 Correct 3 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 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 19 ms 848 KB Output is correct
28 Correct 21 ms 848 KB Output is correct
29 Correct 17 ms 848 KB Output is correct
30 Correct 24 ms 848 KB Output is correct
31 Correct 23 ms 848 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 143 ms 37448 KB Output is correct
34 Correct 290 ms 64612 KB Output is correct
35 Correct 164 ms 64412 KB Output is correct
36 Correct 258 ms 64376 KB Output is correct
37 Correct 187 ms 64464 KB Output is correct
38 Correct 172 ms 64432 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 282 ms 29704 KB Output is correct
5 Correct 1043 ms 64528 KB Output is correct
6 Correct 608 ms 10832 KB Output is correct
7 Correct 1122 ms 64556 KB Output is correct
8 Correct 556 ms 22364 KB Output is correct
9 Correct 1141 ms 64368 KB Output is correct
10 Correct 886 ms 64488 KB Output is correct
11 Correct 1081 ms 64432 KB Output is correct
12 Correct 1090 ms 64428 KB Output is correct
13 Correct 996 ms 64480 KB Output is correct
14 Correct 1066 ms 64548 KB Output is correct
15 Correct 900 ms 64484 KB Output is correct
16 Correct 886 ms 64492 KB Output is correct
17 Correct 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 2 ms 208 KB Output is correct
20 Correct 3 ms 336 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 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 19 ms 848 KB Output is correct
28 Correct 21 ms 848 KB Output is correct
29 Correct 17 ms 848 KB Output is correct
30 Correct 24 ms 848 KB Output is correct
31 Correct 23 ms 848 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 143 ms 37448 KB Output is correct
34 Correct 290 ms 64612 KB Output is correct
35 Correct 164 ms 64412 KB Output is correct
36 Correct 258 ms 64376 KB Output is correct
37 Correct 187 ms 64464 KB Output is correct
38 Correct 172 ms 64432 KB Output is correct
39 Correct 0 ms 208 KB Output is correct
40 Correct 0 ms 208 KB Output is correct
41 Correct 0 ms 208 KB Output is correct
42 Correct 271 ms 29640 KB Output is correct
43 Correct 821 ms 64444 KB Output is correct
44 Correct 610 ms 10856 KB Output is correct
45 Correct 909 ms 64464 KB Output is correct
46 Correct 545 ms 22356 KB Output is correct
47 Correct 1085 ms 64488 KB Output is correct
48 Correct 791 ms 64452 KB Output is correct
49 Correct 1098 ms 64408 KB Output is correct
50 Correct 1071 ms 64456 KB Output is correct
51 Correct 1052 ms 64444 KB Output is correct
52 Correct 901 ms 64420 KB Output is correct
53 Correct 904 ms 64484 KB Output is correct
54 Correct 849 ms 64536 KB Output is correct
55 Correct 0 ms 208 KB Output is correct
56 Incorrect 1352 ms 64168 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 211 ms 51372 KB Output is correct
4 Correct 969 ms 64524 KB Output is correct
5 Correct 735 ms 32500 KB Output is correct
6 Correct 895 ms 64388 KB Output is correct
7 Correct 663 ms 44104 KB Output is correct
8 Correct 946 ms 64456 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Incorrect 2 ms 208 KB Output isn't correct
14 Halted 0 ms 0 KB -