oj.uz

Submission #731334

# Submission time Handle Problem Language Result Execution time Memory
731334 2023-04-27T10:25:55 Z Magikarp4000 Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 82568 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;
  while (x < c) {
    if ((c <= v[x][0] && v[x][0] <= d) || (c <= v[x][1] && v[x][1] <= d)) return res+1;
    if (h[v[x][0]] > mx) break;
    x = v[x][0];
    res++;
  }
  // 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1126 ms 65828 KB Output is correct
4 Execution timed out 4067 ms 82492 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 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 3 ms 336 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 336 KB Output is correct
2 Correct 1 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 3 ms 336 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 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 1 ms 336 KB Output is correct
5 Correct 153 ms 65216 KB Output is correct
6 Correct 155 ms 80920 KB Output is correct
7 Correct 82 ms 41628 KB Output is correct
8 Correct 156 ms 80920 KB Output is correct
9 Correct 25 ms 12448 KB Output is correct
10 Correct 168 ms 80916 KB Output is correct
11 Correct 150 ms 82568 KB Output is correct
12 Incorrect 144 ms 82088 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 267 ms 37152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 267 ms 37152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1126 ms 65828 KB Output is correct
4 Execution timed out 4067 ms 82492 KB Time limit exceeded
5 Halted 0 ms 0 KB -