oj.uz

Submission #561984

# Submission time Handle Problem Language Result Execution time Memory
561984 2022-05-14T02:56:45 Z ian2024 Rainforest Jumps (APIO21_jumps) C++14
27 / 100
 1096 ms 69292 KB 
#include <bits/stdc++.h>

using namespace std;

struct C_HASH {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef long long ll;

const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1000000007;

#define SIZE(a) (int)(a).size()
#define endl '\n'
#define all(x) x.begin(), x.end()
#define ALL(x) begin(x), end(x)

int pos[200005];
int h[200005];
int lo[200005][18];
int hi[200005][18];
int le[200005][18];
int ri[200005][18];
void init(int N, std::vector<int> H) {
  for (int i = 0; i < 200005; ++i) {
    for (int j = 0; j < 18; ++j) {
      lo[i][j] = INF;
      hi[i][j] = INF;
      le[i][j] = INF;
      ri[i][j] = INF;
    }
  }

  for (int i = 0; i < N; ++i) {
    h[i] = H[i];
    pos[H[i]] = i;
  }

  set<int> s;
  for (int i = N; i >= 1; --i) {
    s.insert(pos[i]);
    auto l = s.lower_bound(pos[i]);
    if (l != s.begin()) {
      l--;
      le[i][0] = H[*l];
    }
    auto r = s.upper_bound(pos[i]);
    if (r != s.end()) ri[i][0] = H[*r];
    hi[i][0] = max(le[i][0], ri[i][0]);
    lo[i][0] = min(le[i][0], ri[i][0]);
  }

  for (int j = 1; j < 18; ++j) {
    for (int i = 1; i <= N; ++i) {
      if (lo[i][j - 1] != INF) lo[i][j] = lo[lo[i][j - 1]][j - 1];
      if (hi[i][j - 1] != INF) hi[i][j] = hi[hi[i][j - 1]][j - 1];
      if (le[i][j - 1] != INF) le[i][j] = le[le[i][j - 1]][j - 1];
      if (ri[i][j - 1] != INF) ri[i][j] = ri[ri[i][j - 1]][j - 1];
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  int jumps = 0;
  int curr = h[B];
  for (int i = 17; i >= 0; --i) {
  	if (le[curr][i] != INF and pos[le[curr][i]] >= A and curr < h[C]) curr = le[curr][i];
  }
  
  for (int i = 17; i >= 0; --i) {
    if (hi[curr][i] <= h[C]) {
      curr = hi[curr][i];
      jumps += (1 << i);
    }
  }

  for (int i = 17; i >= 0; --i) {
    if (lo[curr][i] <= h[C]) {
      curr = lo[curr][i];
      jumps += (1 << i);
    }
  }

  if (curr != h[C]) return -1;
  return jumps;
}

#ifdef LOCAL_PROJECT
int main() {
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int A, B, C, D;
    assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
    printf("%d\n", minimum_jumps(A, B, C, D));
  }
  return 0;
}
#else
#include "jumps.h"
#define cerr \
  if (false) cerr
#endif

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56656 KB Output is correct
2 Correct 26 ms 56600 KB Output is correct
3 Correct 239 ms 66628 KB Output is correct
4 Correct 906 ms 69192 KB Output is correct
5 Correct 827 ms 62916 KB Output is correct
6 Correct 1040 ms 69064 KB Output is correct
7 Correct 783 ms 65220 KB Output is correct
8 Correct 1075 ms 69184 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 56556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 56556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 56656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56676 KB Output is correct
2 Correct 33 ms 56584 KB Output is correct
3 Correct 27 ms 56600 KB Output is correct
4 Correct 238 ms 62312 KB Output is correct
5 Correct 1042 ms 69164 KB Output is correct
6 Correct 524 ms 58644 KB Output is correct
7 Correct 1012 ms 69064 KB Output is correct
8 Correct 533 ms 60972 KB Output is correct
9 Correct 908 ms 69188 KB Output is correct
10 Correct 1047 ms 69192 KB Output is correct
11 Correct 951 ms 69064 KB Output is correct
12 Correct 1022 ms 69160 KB Output is correct
13 Correct 1022 ms 69164 KB Output is correct
14 Correct 954 ms 69180 KB Output is correct
15 Correct 792 ms 69064 KB Output is correct
16 Correct 980 ms 69184 KB Output is correct
17 Correct 27 ms 56656 KB Output is correct
18 Correct 26 ms 56648 KB Output is correct
19 Correct 29 ms 56536 KB Output is correct
20 Correct 29 ms 56552 KB Output is correct
21 Correct 32 ms 56648 KB Output is correct
22 Correct 29 ms 56612 KB Output is correct
23 Correct 29 ms 56616 KB Output is correct
24 Correct 28 ms 56656 KB Output is correct
25 Correct 27 ms 56584 KB Output is correct
26 Correct 28 ms 56620 KB Output is correct
27 Correct 44 ms 56684 KB Output is correct
28 Correct 45 ms 56784 KB Output is correct
29 Correct 47 ms 56676 KB Output is correct
30 Correct 46 ms 56728 KB Output is correct
31 Correct 44 ms 56784 KB Output is correct
32 Correct 28 ms 56596 KB Output is correct
33 Correct 131 ms 63816 KB Output is correct
34 Correct 237 ms 69232 KB Output is correct
35 Correct 193 ms 69164 KB Output is correct
36 Correct 201 ms 69060 KB Output is correct
37 Correct 225 ms 69168 KB Output is correct
38 Correct 185 ms 69160 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56676 KB Output is correct
2 Correct 33 ms 56584 KB Output is correct
3 Correct 27 ms 56600 KB Output is correct
4 Correct 238 ms 62312 KB Output is correct
5 Correct 1042 ms 69164 KB Output is correct
6 Correct 524 ms 58644 KB Output is correct
7 Correct 1012 ms 69064 KB Output is correct
8 Correct 533 ms 60972 KB Output is correct
9 Correct 908 ms 69188 KB Output is correct
10 Correct 1047 ms 69192 KB Output is correct
11 Correct 951 ms 69064 KB Output is correct
12 Correct 1022 ms 69160 KB Output is correct
13 Correct 1022 ms 69164 KB Output is correct
14 Correct 954 ms 69180 KB Output is correct
15 Correct 792 ms 69064 KB Output is correct
16 Correct 980 ms 69184 KB Output is correct
17 Correct 27 ms 56656 KB Output is correct
18 Correct 26 ms 56648 KB Output is correct
19 Correct 29 ms 56536 KB Output is correct
20 Correct 29 ms 56552 KB Output is correct
21 Correct 32 ms 56648 KB Output is correct
22 Correct 29 ms 56612 KB Output is correct
23 Correct 29 ms 56616 KB Output is correct
24 Correct 28 ms 56656 KB Output is correct
25 Correct 27 ms 56584 KB Output is correct
26 Correct 28 ms 56620 KB Output is correct
27 Correct 44 ms 56684 KB Output is correct
28 Correct 45 ms 56784 KB Output is correct
29 Correct 47 ms 56676 KB Output is correct
30 Correct 46 ms 56728 KB Output is correct
31 Correct 44 ms 56784 KB Output is correct
32 Correct 28 ms 56596 KB Output is correct
33 Correct 131 ms 63816 KB Output is correct
34 Correct 237 ms 69232 KB Output is correct
35 Correct 193 ms 69164 KB Output is correct
36 Correct 201 ms 69060 KB Output is correct
37 Correct 225 ms 69168 KB Output is correct
38 Correct 185 ms 69160 KB Output is correct
39 Correct 26 ms 56588 KB Output is correct
40 Correct 26 ms 56600 KB Output is correct
41 Correct 27 ms 56656 KB Output is correct
42 Correct 251 ms 62332 KB Output is correct
43 Correct 938 ms 69184 KB Output is correct
44 Correct 561 ms 58732 KB Output is correct
45 Correct 929 ms 69128 KB Output is correct
46 Correct 569 ms 60968 KB Output is correct
47 Correct 1018 ms 69152 KB Output is correct
48 Correct 1096 ms 69152 KB Output is correct
49 Correct 1012 ms 69068 KB Output is correct
50 Correct 1061 ms 69064 KB Output is correct
51 Correct 1057 ms 69164 KB Output is correct
52 Correct 1062 ms 69292 KB Output is correct
53 Correct 960 ms 69160 KB Output is correct
54 Correct 969 ms 69164 KB Output is correct
55 Correct 26 ms 56628 KB Output is correct
56 Incorrect 284 ms 69136 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56656 KB Output is correct
2 Correct 26 ms 56600 KB Output is correct
3 Correct 239 ms 66628 KB Output is correct
4 Correct 906 ms 69192 KB Output is correct
5 Correct 827 ms 62916 KB Output is correct
6 Correct 1040 ms 69064 KB Output is correct
7 Correct 783 ms 65220 KB Output is correct
8 Correct 1075 ms 69184 KB Output is correct
9 Incorrect 30 ms 56556 KB Output isn't correct
10 Halted 0 ms 0 KB -