oj.uz

Submission #567287

# Submission time Handle Problem Language Result Execution time Memory
567287 2022-05-23T10:02:27 Z Bill_00 Rainforest Jumps (APIO21_jumps) C++14
27 / 100
 1207 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 lll = A, rrr = B, pos;
    while(lll < rrr){
      int mmm = lll + rrr >> 1;
      pos = query(1, 1, n, mmm, B);
      if(h[pos] > h[y]){
        lll = mmm + 1;
      }
      else rrr = mmm;
    }
    pos = lll;
    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;
      |           ~~^~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:92:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |       int mmm = lll + rrr >> 1;
      |                 ~~~~^~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 224 ms 36764 KB Output is correct
4 Correct 1207 ms 45364 KB Output is correct
5 Correct 1008 ms 22972 KB Output is correct
6 Correct 1203 ms 45364 KB Output is correct
7 Correct 844 ms 31780 KB Output is correct
8 Correct 1138 ms 45344 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 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 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 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 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 1 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 208 KB Output is correct
5 Correct 107 ms 36280 KB Output is correct
6 Correct 121 ms 44592 KB Output is correct
7 Correct 60 ms 22956 KB Output is correct
8 Correct 111 ms 44568 KB Output is correct
9 Correct 14 ms 6812 KB Output is correct
10 Correct 116 ms 44624 KB Output is correct
11 Correct 118 ms 45332 KB Output is correct
12 Incorrect 115 ms 45208 KB Output isn't correct
13 Halted 0 ms 0 KB -

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 0 ms 208 KB Output is correct
4 Correct 282 ms 20660 KB Output is correct
5 Correct 1018 ms 44616 KB Output is correct
6 Correct 525 ms 7760 KB Output is correct
7 Correct 1108 ms 44576 KB Output is correct
8 Correct 474 ms 15892 KB Output is correct
9 Correct 942 ms 44700 KB Output is correct
10 Correct 1138 ms 45364 KB Output is correct
11 Correct 1151 ms 45256 KB Output is correct
12 Correct 1072 ms 45336 KB Output is correct
13 Correct 886 ms 44572 KB Output is correct
14 Correct 934 ms 45048 KB Output is correct
15 Correct 1112 ms 45384 KB Output is correct
16 Correct 935 ms 45448 KB Output is correct
17 Correct 0 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 4 ms 336 KB Output is correct
21 Correct 3 ms 336 KB Output is correct
22 Correct 3 ms 336 KB Output is correct
23 Correct 3 ms 336 KB Output is correct
24 Correct 1 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 18 ms 720 KB Output is correct
28 Correct 20 ms 720 KB Output is correct
29 Correct 19 ms 720 KB Output is correct
30 Correct 20 ms 720 KB Output is correct
31 Correct 10 ms 720 KB Output is correct
32 Correct 0 ms 336 KB Output is correct
33 Correct 67 ms 25796 KB Output is correct
34 Correct 113 ms 44620 KB Output is correct
35 Correct 111 ms 45220 KB Output is correct
36 Correct 115 ms 44612 KB Output is correct
37 Correct 115 ms 44972 KB Output is correct
38 Correct 107 ms 45448 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 0 ms 208 KB Output is correct
4 Correct 282 ms 20660 KB Output is correct
5 Correct 1018 ms 44616 KB Output is correct
6 Correct 525 ms 7760 KB Output is correct
7 Correct 1108 ms 44576 KB Output is correct
8 Correct 474 ms 15892 KB Output is correct
9 Correct 942 ms 44700 KB Output is correct
10 Correct 1138 ms 45364 KB Output is correct
11 Correct 1151 ms 45256 KB Output is correct
12 Correct 1072 ms 45336 KB Output is correct
13 Correct 886 ms 44572 KB Output is correct
14 Correct 934 ms 45048 KB Output is correct
15 Correct 1112 ms 45384 KB Output is correct
16 Correct 935 ms 45448 KB Output is correct
17 Correct 0 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 4 ms 336 KB Output is correct
21 Correct 3 ms 336 KB Output is correct
22 Correct 3 ms 336 KB Output is correct
23 Correct 3 ms 336 KB Output is correct
24 Correct 1 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 18 ms 720 KB Output is correct
28 Correct 20 ms 720 KB Output is correct
29 Correct 19 ms 720 KB Output is correct
30 Correct 20 ms 720 KB Output is correct
31 Correct 10 ms 720 KB Output is correct
32 Correct 0 ms 336 KB Output is correct
33 Correct 67 ms 25796 KB Output is correct
34 Correct 113 ms 44620 KB Output is correct
35 Correct 111 ms 45220 KB Output is correct
36 Correct 115 ms 44612 KB Output is correct
37 Correct 115 ms 44972 KB Output is correct
38 Correct 107 ms 45448 KB Output is correct
39 Correct 0 ms 336 KB Output is correct
40 Correct 1 ms 208 KB Output is correct
41 Correct 0 ms 208 KB Output is correct
42 Correct 274 ms 20640 KB Output is correct
43 Correct 911 ms 44584 KB Output is correct
44 Correct 548 ms 7780 KB Output is correct
45 Correct 842 ms 44608 KB Output is correct
46 Correct 347 ms 15844 KB Output is correct
47 Correct 807 ms 44576 KB Output is correct
48 Correct 998 ms 45476 KB Output is correct
49 Correct 1128 ms 45292 KB Output is correct
50 Correct 1108 ms 45240 KB Output is correct
51 Correct 998 ms 44620 KB Output is correct
52 Correct 1024 ms 45052 KB Output is correct
53 Correct 907 ms 45344 KB Output is correct
54 Correct 1016 ms 45384 KB Output is correct
55 Correct 0 ms 208 KB Output is correct
56 Incorrect 174 ms 44448 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 208 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 224 ms 36764 KB Output is correct
4 Correct 1207 ms 45364 KB Output is correct
5 Correct 1008 ms 22972 KB Output is correct
6 Correct 1203 ms 45364 KB Output is correct
7 Correct 844 ms 31780 KB Output is correct
8 Correct 1138 ms 45344 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Incorrect 3 ms 208 KB Output isn't correct
14 Halted 0 ms 0 KB -