이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x, y) x = max(x, y)
#define mup(x, y) x = min(x, y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define ensure(...) if (!(__VA_ARGS__)) { fprintf(stderr, "Error in %dth line.", __LINE__), exit(-1); }
template <const int N>
struct segtree {
int t[2*N]{};
int &operator [] (int i){ return t[N+i]; }
void build() {
per(i,1,N-1) t[i] = max(t[2*i],t[2*i+1]);
}
int Max(int a, int b) {
int res = 0;
for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
if (a&1) Mup(res,t[a]);
if (~b&1) Mup(res,t[b]);
}
return res;
}
};
const int N = 2e5;
vi adj[N];
int Mj[N][20], mj[N][20], lj[N][20], rj[N][20], Arg[N+1];
segtree<N> h;
void construct_graph(int n, vi &H) {
stack<int> S;
rep(i,0,n-1) {
while (not S.empty() and H[S.top()] < H[i]) S.pop();
if (not S.empty()) adj[i].push_back(S.top());
S.push(i);
}
while (not S.empty()) S.pop();
per(i,0,n-1) {
while (not S.empty() and H[S.top()] < H[i]) S.pop();
if (not S.empty()) adj[i].push_back(S.top());
S.push(i);
}
}
void construct_sparsetable(int n, vi &H) {
rep(i,0,n-1) {
ensure(not adj[i].empty() or H[i] == n);
if (adj[i].empty()) {
Mj[i][0] = mj[0][i] = lj[i][0] = rj[i][0] = i;
}
else if (siz(adj[i]) == 1) {
Mj[i][0] = mj[i][0] = adj[i][0];
lj[i][0] = adj[i][0] < i ? adj[i][0] : i;
rj[i][0] = adj[i][0] > i ? adj[i][0] : i;
}
else if (siz(adj[i]) == 2) {
Mj[i][0] = adj[i][0], mj[i][0] = adj[i][1];
if (H[Mj[i][0]] < H[mj[i][0]]) swap(Mj[i][0],mj[i][0]);
lj[i][0] = adj[i][0], rj[i][0] = adj[i][1];
if (lj[i][0] > rj[i][0]) swap(lj[i][0],rj[i][0]);
}
else ensure(0);
}
rep(k,1,19) rep(i,0,n-1) {
Mj[i][k] = Mj[Mj[i][k-1]][k-1];
mj[i][k] = mj[mj[i][k-1]][k-1];
lj[i][k] = lj[lj[i][k-1]][k-1];
rj[i][k] = rj[rj[i][k-1]][k-1];
}
}
void init(int N, vi H) {
construct_graph(N, H);
construct_sparsetable(N, H);
rep(i,0,N-1) h[i] = H[i], Arg[H[i]] = i;
h.build();
}
int A, B, C, D, hurdle;
const int INF = 1e9;
int minimum_jumps(int A, int B, int C, int D) {
hurdle = h.Max(B,C-1);
if (hurdle > h.Max(C,D)) return -1;
int x = B, ans = INF;
per(i,0,19) while (A <= lj[x][i]&&lj[x][i] < x and h[lj[x][i]] < hurdle) x = lj[x][i];
{ // Case. (나)
int y = lj[x][0];
if (A <= y&&y < x) {
ensure(h[y] >= hurdle);
y = rj[y][0];
if (C <= y&&y <= D) return 1;
}
}
{ // Case. (가)&(다)
if (C <= rj[B][0]&&rj[B][0] <= D) return 1;
int y = x, d = 0;
per(i,0,19) while (y < C && y != Mj[y][i] and h[Mj[y][i]] < hurdle) {
x = Mj[x][i], d += int(!(A<=Mj[x][i]&&Mj[x][i]<=B))<<i;
}
if (h[Mj[y][0]] >= hurdle) {
int z = Mj[y][0];
if (z < C) {
if (C <= rj[z][0]&&rj[z][0] <= D) {
return d+1+(z!=y);
}
} else {
if (C <= z&&z <= D) {
return d+(z!=y);
}
}
}
per(i,0,19) while (y < C && y != mj[y][i] and h[mj[y][i]] < hurdle) {
x = mj[x][i], d += int(!(A<=mj[x][i]&&mj[x][i]<=B))<<i;
}
if (h[mj[y][0]] >= hurdle) {
int z = mj[y][0];
if (z < C) {
if (C <= rj[z][0]&&rj[z][0] <= D) {
return d+1+(z!=y);
}
} else {
if (C <= z&&z <= D) {
return d+(z!=y);
}
}
}
}
ensure(ans < INF);
return ans;
}
#ifdef LOCAL
int main() {
int N, Q;
ensure(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
for (int i = 0; i < N; ++i)
{
ensure(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i)
{
int A, B, C, D;
ensure(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
printf("%d\n", minimum_jumps(A, B, C, D));
}
return 0;
}
#endif
# | 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... |