oj.uz

답안 #731253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731253 2023-04-27T08:22:51 Z Magikarp4000 밀림 점프 (APIO21_jumps) C++17
4 / 100
 1219 ms 82572 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 2e5+1, LOG = 19;
int n;
int v[MAXN][2];
int l[MAXN], r[MAXN];
int jump[MAXN][LOG], jump1[MAXN][LOG], jl[MAXN][LOG], jr[MAXN][LOG];
int sp[MAXN][LOG];
int h[MAXN];
int lg[MAXN];

void init(int N, std::vector<int> H) {
  n = N;
  FOR(i,1,n+1) h[i] = H[i-1];
  FOR(i,2,n+1) lg[i] = lg[i>>1]+1;
  stack<PII> st;
  FOR(i,1,n+1) {
    while (!st.empty() && st.top().F <= h[i]) st.pop();
    if (st.empty()) l[i] = 0;
    else l[i] = st.top().S;
    st.push({h[i],i});
  }
  while (!st.empty()) st.pop();
  FORR(i,n,0) {
    while (!st.empty() && st.top().F <= h[i]) st.pop();
    if (st.empty()) r[i] = 0;
    else r[i] = st.top().S;
    st.push({h[i],i});
  }
  
  FOR(i,1,n+1) {
    v[i][0] = l[i];
    v[i][1] = r[i];
    if (h[l[i]] < h[r[i]]) swap(v[i][0], v[i][1]);
  }
  // FOR(i,1,n+1) cout << v[i][0] << ' ';
  // cout << ln;
  // FOR(i,1,n+1) cout << v[i][1] << ' ';
  // cout << ln;
  FOR(i,1,n+1) {
    jump[i][0] = v[i][0];
    jump1[i][0] = v[i][1];
    jl[i][0] = l[i];
    jr[i][0] = r[i];
    sp[i][0] = h[i];
  }
  FOR(j,1,LOG) {
    FOR(i,1,n+1) {
      jump[i][j] = jump[jump[i][j-1]][j-1];
      jump1[i][j] = jump1[jump1[i][j-1]][j-1];
      jl[i][j] = jl[jl[i][j-1]][j-1];
      jr[i][j] = jr[jr[i][j-1]][j-1];
      if (i+(1<<(j-1)) <= n) sp[i][j] = max(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
      else sp[i][j] = sp[i][j-1];
    }
  }
}

int query(int a, int b) {
  int len = lg[b-a+1];
  return max(sp[a][len], sp[b-(1<<len)+1][len]);
}

int minimum_jumps(int a, int b, int c, int d) {
  a++; b++; c++; d++;
  //cout << a << ' ' << c << ln;
  int mx = query(c,d);
  int res = 0;
  int x = b;
  FORR(j,LOG-1,-1) {
    if (jl[x][j] >= a && h[jl[x][j]] < mx) {
      x = jl[x][j];
    }
  }
  if (h[x] > mx) return -1;
  FORR(j,LOG-1,-1) {
    if ((c <= v[x][0] && v[x][0] <= d) || (c <= v[x][1] && v[x][1] <= d)) return res+1;
    if (jump[x][j] != 0 && jump[x][j] < c && h[jump[x][j]] < mx) {
      res += (1<<j);
      x = jump[x][j];
    }
  }
  FORR(j,LOG-1,-1) {
    if ((c <= v[x][0] && v[x][0] <= d) || (c <= v[x][1] && v[x][1] <= d)) return res+1;
    if (jr[x][j] < c) {
      res += (1<<j);
      x = jr[x][j];
    }
  }
  x = r[x];
  res++;
  // if ((c <= v[x][0] <= d) || (c <= v[x][1] <= d)) return res+1;
  if (x < c || x > d) return -1;
  return res;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 226 ms 65828 KB Output is correct
4 Correct 1068 ms 82568 KB Output is correct
5 Correct 1022 ms 41704 KB Output is correct
6 Correct 1141 ms 82564 KB Output is correct
7 Correct 952 ms 56548 KB Output is correct
8 Correct 1219 ms 82572 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 133 ms 65096 KB Output is correct
6 Correct 154 ms 80960 KB Output is correct
7 Correct 90 ms 41544 KB Output is correct
8 Correct 150 ms 80804 KB Output is correct
9 Correct 21 ms 12460 KB Output is correct
10 Correct 154 ms 80804 KB Output is correct
11 Correct 146 ms 82488 KB Output is correct
12 Incorrect 153 ms 82124 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 289 ms 37116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 289 ms 37116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 226 ms 65828 KB Output is correct
4 Correct 1068 ms 82568 KB Output is correct
5 Correct 1022 ms 41704 KB Output is correct
6 Correct 1141 ms 82564 KB Output is correct
7 Correct 952 ms 56548 KB Output is correct
8 Correct 1219 ms 82572 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Incorrect 2 ms 336 KB Output isn't correct
14 Halted 0 ms 0 KB -