oj.uz

Submission #567249

# Submission time Handle Problem Language Result Execution time Memory
567249 2022-05-23T09:46:30 Z Bill_00 Rainforest Jumps (APIO21_jumps) C++14
27 / 100
 1300 ms 45476 KB 
#include "jumps.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

int best[200005][25], rightt[200005][25], h[200005], n, tallest[2000000], L[200005];
void update(int id, int l, int r, int pos, int val){
  if(h[val] > h[tallest[id]]){
    tallest[id] = val;
  }
  if(l == r){
    return;
  }
  int m = l + r >> 1;
  if(m >= pos){
    update(id * 2, l, m, pos, val);
  }
  else update(id * 2 + 1, m + 1, r, pos, val);
}

int query(int id, int l, int r, int lef, int rig){
  if(lef > rig) return 200004;
  if(r < lef || rig < l) return 200004;
  if(lef <= l && r <= rig) return tallest[id];
  int m = l + r >> 1;
  int lll = query(id * 2, l, m, lef, rig);
  int rrr = query(id * 2 + 1, m + 1, r, lef, rig);
  return (h[lll] > h[rrr] ? lll : rrr);
}
void init(int N, vector<int> H){
  n = N;
  for(int i = 1; i <= n; i++){
    h[i] = H[i - 1];
    update(1, 1, n, i, i);
  }
  stack<int> s, t;
  h[n + 1] = 1e9;
  s.push(n + 1);
  for(int i = n; i >= 1; i--){
    while(h[s.top()] < h[i]){
      s.pop();
    }
    rightt[i][0] = s.top();
    s.push(i);
  }
  t.push(0);
  h[0] = 1e9;
  for(int i = 1; i <= n; i++){
    while(h[t.top()] < h[i]){
      t.pop();
    }
    L[i] = t.top();
    t.push(i);
  }
  for(int i = 1; i <= n; i++){
    if(h[L[i]] < 1e9 && h[rightt[i][0]] < 1e9){
      best[i][0] = (h[L[i]] > h[rightt[i][0]] ? L[i] : rightt[i][0]);
    }
    else{
      if(h[L[i]] < 1e9){
        best[i][0] = L[i];
      }
      else{
        if(h[rightt[i][0]] < 1e9){
          best[i][0] = rightt[i][0];
        }
        else best[i][0] = 0;
      }
    }
  }
  rightt[n + 1][0] = n + 1;
  for(int j = 1; j <= 20; j++){
    for(int i = 0; i <= n + 1; i++){
      rightt[i][j] = rightt[rightt[i][j - 1]][j - 1];
      best[i][j] = best[best[i][j - 1]][j - 1];
    }
  }
}

int minimum_jumps(int A, int B, int C, int D){
  A++, B++, C++, D++;
  int x = query(1, 1, n, B + 1, C - 1);
  int y = query(1, 1, n, C, D);
  // cout << x << ' ' << y << '\n';
  if(h[x] > h[y]) return -1;
  if(h[B] > h[y]) return -1;
  int z = query(1, 1, n, A, B);
  if(h[z] > h[y]){
    int pos = query(1, 1, n, z + 1, B);
    int ans = 0;
    for(int i = 20; i >= 0; i--){
      if(C > rightt[pos][i]){
        ans += (1 << i);
        pos = rightt[pos][i];
      } 
    }
    return ans + 1;
  }
  else{
    int ans = 0;
    int pos = z;
    // cout << pos << ' ' << x << '\n';
    for(int i = 20; i >= 0; i--){
      if(h[best[pos][i]] < h[x]){
        pos = best[pos][i];
        ans += (1 << i);
      }
    }
    // cout << best[pos][0] << ' ' << ans << '\n';
    if(h[best[pos][0]] < h[y]){
      if(best[pos][0] >= C && best[pos][0] <= D) ans ++;
      else ans += 2;
    }
    else{
      for(int i = 20; i >= 0; i--){
        // cout << pos << '\n';
        if(C > rightt[pos][i]){
          ans += (1 << i);
          pos = rightt[pos][i];
        }
      }
      ans++;
    }
    return ans;
  }
}

Compilation message

jumps.cpp: In function 'void update(int, int, int, int, int)':
jumps.cpp:14:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |   int m = l + r >> 1;
      |           ~~^~~
jumps.cpp: In function 'int query(int, int, int, int, int)':
jumps.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   int m = l + r >> 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 177 ms 36624 KB Output is correct
4 Correct 1221 ms 45368 KB Output is correct
5 Correct 1055 ms 22940 KB Output is correct
6 Correct 1300 ms 45444 KB Output is correct
7 Correct 885 ms 31688 KB Output is correct
8 Correct 1146 ms 45384 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 1 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 3 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 1 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 3 ms 208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
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 336 KB Output is correct
5 Correct 100 ms 36260 KB Output is correct
6 Correct 133 ms 44552 KB Output is correct
7 Correct 60 ms 22948 KB Output is correct
8 Correct 115 ms 44620 KB Output is correct
9 Correct 13 ms 6968 KB Output is correct
10 Correct 111 ms 44624 KB Output is correct
11 Correct 137 ms 45460 KB Output is correct
12 Correct 114 ms 45208 KB Output is correct
13 Correct 133 ms 45212 KB Output is correct
14 Correct 116 ms 44600 KB Output is correct
15 Correct 128 ms 45052 KB Output is correct
16 Correct 104 ms 45352 KB Output is correct
17 Correct 131 ms 45368 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 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 Incorrect 1 ms 336 KB Output isn't correct
23 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 0 ms 336 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 288 ms 20632 KB Output is correct
5 Correct 1105 ms 44628 KB Output is correct
6 Correct 557 ms 7756 KB Output is correct
7 Correct 721 ms 44508 KB Output is correct
8 Correct 467 ms 15784 KB Output is correct
9 Correct 972 ms 44584 KB Output is correct
10 Correct 1128 ms 45476 KB Output is correct
11 Correct 1258 ms 45352 KB Output is correct
12 Correct 1070 ms 45260 KB Output is correct
13 Correct 1180 ms 44576 KB Output is correct
14 Correct 1284 ms 44976 KB Output is correct
15 Correct 1070 ms 45444 KB Output is correct
16 Correct 1054 ms 45452 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 4 ms 336 KB Output is correct
21 Correct 5 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 4 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 17 ms 720 KB Output is correct
28 Correct 21 ms 720 KB Output is correct
29 Correct 24 ms 688 KB Output is correct
30 Correct 12 ms 720 KB Output is correct
31 Correct 30 ms 720 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 76 ms 25808 KB Output is correct
34 Correct 145 ms 44616 KB Output is correct
35 Correct 139 ms 45328 KB Output is correct
36 Correct 114 ms 44488 KB Output is correct
37 Correct 132 ms 44956 KB Output is correct
38 Correct 125 ms 45388 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 0 ms 336 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 288 ms 20632 KB Output is correct
5 Correct 1105 ms 44628 KB Output is correct
6 Correct 557 ms 7756 KB Output is correct
7 Correct 721 ms 44508 KB Output is correct
8 Correct 467 ms 15784 KB Output is correct
9 Correct 972 ms 44584 KB Output is correct
10 Correct 1128 ms 45476 KB Output is correct
11 Correct 1258 ms 45352 KB Output is correct
12 Correct 1070 ms 45260 KB Output is correct
13 Correct 1180 ms 44576 KB Output is correct
14 Correct 1284 ms 44976 KB Output is correct
15 Correct 1070 ms 45444 KB Output is correct
16 Correct 1054 ms 45452 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 4 ms 336 KB Output is correct
21 Correct 5 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 4 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 17 ms 720 KB Output is correct
28 Correct 21 ms 720 KB Output is correct
29 Correct 24 ms 688 KB Output is correct
30 Correct 12 ms 720 KB Output is correct
31 Correct 30 ms 720 KB Output is correct
32 Correct 0 ms 208 KB Output is correct
33 Correct 76 ms 25808 KB Output is correct
34 Correct 145 ms 44616 KB Output is correct
35 Correct 139 ms 45328 KB Output is correct
36 Correct 114 ms 44488 KB Output is correct
37 Correct 132 ms 44956 KB Output is correct
38 Correct 125 ms 45388 KB Output is correct
39 Correct 1 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 277 ms 20552 KB Output is correct
43 Correct 1192 ms 44600 KB Output is correct
44 Correct 612 ms 7760 KB Output is correct
45 Correct 885 ms 44624 KB Output is correct
46 Correct 555 ms 15776 KB Output is correct
47 Correct 1002 ms 44600 KB Output is correct
48 Correct 1270 ms 45448 KB Output is correct
49 Correct 1180 ms 45392 KB Output is correct
50 Correct 1109 ms 45388 KB Output is correct
51 Correct 1180 ms 44620 KB Output is correct
52 Correct 1069 ms 45052 KB Output is correct
53 Correct 913 ms 45428 KB Output is correct
54 Correct 1156 ms 45348 KB Output is correct
55 Correct 0 ms 208 KB Output is correct
56 Incorrect 176 ms 44440 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 177 ms 36624 KB Output is correct
4 Correct 1221 ms 45368 KB Output is correct
5 Correct 1055 ms 22940 KB Output is correct
6 Correct 1300 ms 45444 KB Output is correct
7 Correct 885 ms 31688 KB Output is correct
8 Correct 1146 ms 45384 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Incorrect 3 ms 208 KB Output isn't correct
14 Halted 0 ms 0 KB -