oj.uz

답안 #541958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
541958 2022-03-24T21:47:28 Z aryan12 밀림 점프 (APIO21_jumps) C++17
23 / 100
 4000 ms 46256 KB 
#include "jumps.h"
#include <vector>
using namespace std;
#include <bits/stdc++.h>

const int MAXN = 2e5 + 5;
int DP_Min[19][MAXN], DP_Max[19][MAXN];
int seg[MAXN * 4];
vector<int> INPUT;
map<int, int> revcc;
int okN;

void Build(int l, int r, int pos) {
  if(l == r) {
    seg[pos] = INPUT[l - 1];
    return;
  }
  int mid = (l + r) >> 1;
  Build(l, mid, pos * 2);
  Build(mid + 1, r, pos * 2 + 1);
  seg[pos] = max(seg[pos * 2], seg[pos * 2 + 1]);
}

pair<int, int> Query(int l, int r, int pos, int ql, int qr, int qval) {
  if(ql > r || l > qr) {
    //cout << "l = " << l << ", r = " << r << ", there {-1, -1}\n";
    return {0, 0};
  }
  if(l == r) {
    if(seg[pos] >= qval) {
      //cout << "l = " << l << ", r = " << r << ", here {-1, -1}\n";
      return {-1, -1};
    }
    //cout << "l = " << l << ", r = " << r << ", {" << seg[pos] << ", " << seg[pos] << "}\n";
    return {seg[pos], seg[pos]};
  }
  int mid = (l + r) >> 1;
  pair<int, int> x = Query(mid + 1, r, pos * 2 + 1, ql, qr, qval);
  if(x.second == -1) {
    //cout << "l = " << l << ", r = " << r << ", aftermid {" << x.first << ", -1}\n";
    return x;
  }
  pair<int, int> y = Query(l, mid, pos * 2, ql, qr, qval);
  if(y.second == -1) {
    //cout << "l = " << l << ", r = " << r << ", {" << max(y.first, x.first) << ", " << y.second << "}\n";
    return {max(y.first, x.first), -1};
  }
  //cout << "l = " << l << ", r = " << r << ", {" << max(y.first, x.first) << ", " << max(y.second, x.second) << "}\n";
  return {max(y.first, x.first), max(y.second, x.second)};
}

void init(int N, vector<int> H) {
  okN = N;
  vector<int> L(N), R(N);
  stack<int> q;
  for(int i = 0; i < N; i++) {
    revcc[H[i]] = i;
    INPUT.push_back(H[i]);
    while(!q.empty() && H[q.top()] <= H[i]) {
      q.pop();
    }
    if(q.empty()) {
      L[i] = -1;
    }
    else {
      L[i] = q.top();
    }
    q.push(i);
  }
  Build(1, N, 1);
  while(!q.empty()) {
    q.pop();
  }
  for(int i = N - 1; i >= 0; i--) {
    while(!q.empty() && H[q.top()] <= H[i]) {
      q.pop();
    }
    if(q.empty()) {
      R[i] = N;
    }
    else {
      R[i] = q.top();
    }
    q.push(i);
  }
  for(int i = 0; i < N; i++) {
    if(L[i] == -1 && R[i] == N) {
      DP_Min[0][i] = -1;
      DP_Max[0][i] = -1;
    }
    else if(L[i] == -1 || R[i] == N) {
      if(L[i] == -1) {
        DP_Min[0][i] = R[i];
        DP_Max[0][i] = R[i];
      }
      else {
        DP_Min[0][i] = L[i];
        DP_Max[0][i] = L[i];
      }
    }
    else {
      if(H[L[i]] < H[R[i]]) {
        DP_Min[0][i] = L[i];
        DP_Max[0][i] = R[i];
      }
      else {
        DP_Min[0][i] = R[i];
        DP_Max[0][i] = L[i];
      }
      //DP_Min[0][i] = min(L[i], R[i]);
      //DP_Max[0][i] = max(L[i], R[i]);
    }
  }
  for(int i = 1; i < 19; i++) {
    for(int j = 0; j < N; j++) {
      if(DP_Min[i - 1][j] == -1) {
        DP_Min[i][j] = -1;
      }
      else {
        DP_Min[i][j] = DP_Min[i - 1][DP_Min[i - 1][j]];
      }
      if(DP_Max[i - 1][j] == -1) {
        DP_Max[i][j] = -1;
      }
      else {
        DP_Max[i][j] = DP_Max[i - 1][DP_Max[i - 1][j]];
      }
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  A++;
  B++;
  //cout << "A = " << A << ", B = " << B << ", INPUT[C] = " << INPUT[C] << "\n";
  int pos = Query(1, okN, 1, A, B, INPUT[C]).first;
  A = revcc[pos];
  B = revcc[pos];
  //cout << "A = " << A << ", B = " << B << "\n";
  int ans = 0, cur = B;
  for(int i = 18; i >= 0; i--) {
    if(DP_Max[i][cur] != -1 && INPUT[DP_Max[i][cur]] <= INPUT[C]) {
      //cout << "prev cur = " << cur << "\n";
      ans += (1 << i);
      cur = DP_Max[i][cur];
      //cout << "new cur = " << cur << ", with added answer: " << (1 << i) << "\n";
    }
  }
  for(int i = 18; i >= 0; i--) {
    if(DP_Min[i][cur] != -1 && INPUT[DP_Min[i][cur]] <= INPUT[C]) {
      ans += (1 << i);
      cur = DP_Min[i][cur];
    }
  }
  if(cur != C) return -1;
  return ans;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 3576 ms 37400 KB Output is correct
4 Execution timed out 4003 ms 46124 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 307 ms 21164 KB Output is correct
5 Correct 1020 ms 45328 KB Output is correct
6 Correct 595 ms 8120 KB Output is correct
7 Correct 1053 ms 45360 KB Output is correct
8 Correct 640 ms 16244 KB Output is correct
9 Correct 1069 ms 45392 KB Output is correct
10 Correct 1203 ms 46236 KB Output is correct
11 Correct 1022 ms 46108 KB Output is correct
12 Correct 1151 ms 46120 KB Output is correct
13 Correct 1076 ms 45292 KB Output is correct
14 Correct 962 ms 45780 KB Output is correct
15 Correct 859 ms 46256 KB Output is correct
16 Correct 807 ms 46232 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 2 ms 464 KB Output is correct
21 Correct 2 ms 464 KB Output is correct
22 Correct 2 ms 556 KB Output is correct
23 Correct 2 ms 464 KB Output is correct
24 Correct 2 ms 464 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 1 ms 592 KB Output is correct
27 Correct 11 ms 848 KB Output is correct
28 Correct 18 ms 848 KB Output is correct
29 Correct 27 ms 848 KB Output is correct
30 Correct 19 ms 848 KB Output is correct
31 Correct 17 ms 848 KB Output is correct
32 Correct 0 ms 464 KB Output is correct
33 Correct 71 ms 26420 KB Output is correct
34 Correct 142 ms 45308 KB Output is correct
35 Correct 76 ms 46032 KB Output is correct
36 Correct 118 ms 45368 KB Output is correct
37 Correct 71 ms 45824 KB Output is correct
38 Correct 63 ms 46216 KB Output is correct

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 307 ms 21164 KB Output is correct
5 Correct 1020 ms 45328 KB Output is correct
6 Correct 595 ms 8120 KB Output is correct
7 Correct 1053 ms 45360 KB Output is correct
8 Correct 640 ms 16244 KB Output is correct
9 Correct 1069 ms 45392 KB Output is correct
10 Correct 1203 ms 46236 KB Output is correct
11 Correct 1022 ms 46108 KB Output is correct
12 Correct 1151 ms 46120 KB Output is correct
13 Correct 1076 ms 45292 KB Output is correct
14 Correct 962 ms 45780 KB Output is correct
15 Correct 859 ms 46256 KB Output is correct
16 Correct 807 ms 46232 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Correct 1 ms 464 KB Output is correct
20 Correct 2 ms 464 KB Output is correct
21 Correct 2 ms 464 KB Output is correct
22 Correct 2 ms 556 KB Output is correct
23 Correct 2 ms 464 KB Output is correct
24 Correct 2 ms 464 KB Output is correct
25 Correct 1 ms 464 KB Output is correct
26 Correct 1 ms 592 KB Output is correct
27 Correct 11 ms 848 KB Output is correct
28 Correct 18 ms 848 KB Output is correct
29 Correct 27 ms 848 KB Output is correct
30 Correct 19 ms 848 KB Output is correct
31 Correct 17 ms 848 KB Output is correct
32 Correct 0 ms 464 KB Output is correct
33 Correct 71 ms 26420 KB Output is correct
34 Correct 142 ms 45308 KB Output is correct
35 Correct 76 ms 46032 KB Output is correct
36 Correct 118 ms 45368 KB Output is correct
37 Correct 71 ms 45824 KB Output is correct
38 Correct 63 ms 46216 KB Output is correct
39 Correct 1 ms 464 KB Output is correct
40 Correct 0 ms 464 KB Output is correct
41 Correct 0 ms 464 KB Output is correct
42 Correct 281 ms 21200 KB Output is correct
43 Correct 964 ms 45368 KB Output is correct
44 Correct 665 ms 8032 KB Output is correct
45 Correct 927 ms 45344 KB Output is correct
46 Correct 575 ms 16292 KB Output is correct
47 Correct 967 ms 45340 KB Output is correct
48 Correct 1099 ms 46184 KB Output is correct
49 Correct 1203 ms 46164 KB Output is correct
50 Correct 1083 ms 46012 KB Output is correct
51 Correct 924 ms 45464 KB Output is correct
52 Correct 1006 ms 45740 KB Output is correct
53 Correct 906 ms 46136 KB Output is correct
54 Correct 833 ms 46136 KB Output is correct
55 Correct 1 ms 464 KB Output is correct
56 Correct 177 ms 45320 KB Output is correct
57 Correct 999 ms 45316 KB Output is correct
58 Correct 479 ms 8488 KB Output is correct
59 Correct 977 ms 45448 KB Output is correct
60 Correct 421 ms 16804 KB Output is correct
61 Correct 1006 ms 45492 KB Output is correct
62 Execution timed out 4025 ms 46256 KB Time limit exceeded
63 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 464 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 3576 ms 37400 KB Output is correct
4 Execution timed out 4003 ms 46124 KB Time limit exceeded
5 Halted 0 ms 0 KB -