oj.uz

답안 #562487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
562487 2022-05-14T13:22:51 Z ian2024 밀림 점프 (APIO21_jumps) C++14
4 / 100
 1603 ms 143248 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];
int pi[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;
      pi[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];
    	pi[ri[i][0]][0] = i;
    }
    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];
      if (pi[i][j - 1] != INF) pi[i][j] = pi[pi[i][j - 1]][j - 1];
    }
  }
}
 
int f(int curr, int ed) {
  int jumps = 0;
  for (int i = 17; i >= 0; --i) {
    if (hi[curr][i] <= ed) {
      curr = hi[curr][i];
      jumps += (1 << i);
    }
  }
 
  for (int i = 17; i >= 0; --i) {
    if (lo[curr][i] <= ed) {
      curr = lo[curr][i];
      jumps += (1 << i);
    }
  }
 
  if (curr != ed) return -1;
  return jumps;
}
 
int minimum_jumps(int A, int B, int C, int D) {
  int curr = h[B];
  
  if (B == C - 1) {
  	return pos[ri[curr][0]] <= D ? 1 : -1;
  }
  
  for (int i = 17; i >= 0; --i) {
    if (le[curr][i] != INF and pos[le[curr][i]] >= A and le[curr][i] < h[C])
      curr = le[curr][i];
  }
 
  int rr = h[C];
  for (int i = 17; i >= 0; --i) {
  	if (ri[rr][i] != INF and pos[ri[rr][i]] <= D) rr = ri[rr][i];
  }
  
  int res = f(curr, rr);
  
  for (int x = 17; x >= 0; --x) {
  	if (pi[rr][x] != INF and pos[pi[rr][x]] >= C) {
  		int v = f(curr, pi[rr][x]);
  		if (v != -1) {
  			rr = pi[rr][x];
  			res = v;
  		}
  	}
  }
  
  return res;
}
 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 70716 KB Output is correct
2 Correct 33 ms 70740 KB Output is correct
3 Correct 321 ms 80656 KB Output is correct
4 Correct 1603 ms 83372 KB Output is correct
5 Correct 1312 ms 76976 KB Output is correct
6 Correct 1546 ms 83292 KB Output is correct
7 Correct 1257 ms 79200 KB Output is correct
8 Correct 1544 ms 83228 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 70704 KB Output is correct
2 Correct 34 ms 70704 KB Output is correct
3 Runtime error 104 ms 143176 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 70704 KB Output is correct
2 Correct 34 ms 70704 KB Output is correct
3 Runtime error 104 ms 143176 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 70668 KB Output is correct
2 Correct 46 ms 70728 KB Output is correct
3 Runtime error 103 ms 143248 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 70736 KB Output is correct
2 Runtime error 106 ms 143164 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 70736 KB Output is correct
2 Runtime error 106 ms 143164 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 70716 KB Output is correct
2 Correct 33 ms 70740 KB Output is correct
3 Correct 321 ms 80656 KB Output is correct
4 Correct 1603 ms 83372 KB Output is correct
5 Correct 1312 ms 76976 KB Output is correct
6 Correct 1546 ms 83292 KB Output is correct
7 Correct 1257 ms 79200 KB Output is correct
8 Correct 1544 ms 83228 KB Output is correct
9 Correct 33 ms 70704 KB Output is correct
10 Correct 34 ms 70704 KB Output is correct
11 Runtime error 104 ms 143176 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -