이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct SegmentTree {
int n, h;
vector<pii> arr;
SegmentTree(int _n) : n(_n) {
h = Log2(n);
n = 1 << h;
arr.resize(2*n);
for (int i=n; i<2*n; ++i) arr[i] = { 0, i-n };
for (int i=n-1; i>=0; --i) arr[i] = { 0, arr[2*i].second };
}
void update(int pos, int c) {
pos += n;
arr[pos] = { c, pos-n };
for (pos /= 2; pos > 0; pos /= 2) {
arr[pos] = (arr[2*pos].first > arr[2*pos+1].first ? arr[2*pos] : arr[2*pos+1]);
}
}
pii query(int l, int r) {
l += n, r += n;
pii ret = {0,-1};
for (; l <= r; l/=2, r/=2) {
if (l & 1) ret = (ret.first > arr[l].first ? ret : arr[l]), l++;
if (~r & 1) ret = (ret.first > arr[r].first ? ret : arr[r]), r--;
}
return ret;
}
static int Log2(int x){
int ret = 0;
while (x > (1 << ret)) ret++;
return ret;
}
};
const int MAX_N = 2e5 + 1;
int n;
int h[MAX_N];
vector<int> adj[MAX_N];
int depth[MAX_N];
int large_sparse[18][MAX_N];
int sparse[18][MAX_N];
SegmentTree seg(MAX_N);
void dfs(int here) {
for (int there: adj[here]) {
depth[there] = depth[here] + 1;
dfs(there);
}
}
void init(int N, vector<int> H) {
n = N;
for (int i=0; i<n; ++i) h[i] = H[i];
for (int i=0; i<n; ++i) seg.update(i, h[i]);
vector<pii> nxt(n, {-1,-1});
for (int i=0; i<n; ++i) {
int l = i+1, r = n-1;
while (l < r) {
int m = (l+r)/2;
if (seg.query(i+1, m).first > h[i]) {
r = m;
} else {
l = m+1;
}
}
if (l < n-1 || h[l] >= h[i]) nxt[i].second = l;
}
for (int i=0; i<n; ++i) {
int l = 0, r = i-1;
while (l < r) {
int m = (l+r+1)/2;
if (seg.query(m, i-1).first > h[i]) {
l = m;
} else {
r = m-1;
}
}
if (r > 0 || h[r] >= h[i]) nxt[i].first = r;
}
memset(sparse, -1, sizeof sparse);
memset(large_sparse, -1, sizeof large_sparse);
for (int i=0; i<n; ++i) {
// cout << i << ' ' << nxt[i].first << ' ' << nxt[i].second << endl;
if (nxt[i].first != -1 && nxt[i].second != -1) {
large_sparse[0][i] = (h[nxt[i].first] > h[nxt[i].second] ? nxt[i].first : nxt[i].second);
sparse[0][i] = (h[nxt[i].first] > h[nxt[i].second] ? nxt[i].second : nxt[i].first);
} else {
large_sparse[0][i] = (nxt[i].first == -1 ? nxt[i].second : nxt[i].first);
sparse[0][i] = large_sparse[0][i];
}
if (sparse[0][i] != -1) adj[sparse[0][i]].push_back(i);
// cout << i << ' ' << sparse[0][i] << ' ' << large_sparse[0][i] << endl;
}
for (int i=1; i<18; ++i) {
for (int j=0; j<n; ++j) {
if (sparse[i-1][j] != -1) sparse[i][j] = sparse[i-1][sparse[i-1][j]];
if (large_sparse[i-1][j] != -1) large_sparse[i][j] = large_sparse[i-1][large_sparse[i-1][j]];
}
}
dfs(seg.query(0, n-1).second);
}
bool is_reachable(int here, int par) {
int d = max(0, depth[here] - depth[par]);
for (int i=17; i>=0; --i) {
if (d & (1 << i)) {
here = sparse[i][here];
}
}
return here == par;
}
int onetoone(int from, int to) {
if (!is_reachable(from, to)) return -1;
int ret = 0;
for (int i=17; i>=0; --i) {
if (large_sparse[i][from] != -1 && is_reachable(large_sparse[i][from], to)) {
from = large_sparse[i][from];
ret += (1 << i);
}
}
return ret + depth[from] - depth[to];
}
int minimum_jumps(int A, int B, int C, int D) {
auto[m, midx] = seg.query(B+1, C-1);
if (seg.query(C, D).first < m) return -1;
auto[highest, idx] = seg.query(A, B);
if (highest < m) return onetoone(idx, midx) + 1;
int l = A, r = B;
while (l < r) {
int mid = (l+r+1)/2;
if (seg.query(mid, B).first > m) {
l = mid;
} else {
r = mid-1;
}
}
if (seg.query(C, D).first > h[l]) return 1;
int from = seg.query(r+1, B).second;
// cout << r << ' ' << from << endl;
if (from == -1) return -1;
return onetoone(from, m) + 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |