이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int N;
int P[200005];
int MX[800005];
int L[200005], R[200005];
int par[200005][20];
vector<int> ST[800005];
vector<int> adj[200005];
int UP[200005][20], DN[200005][20];
vector<int> H;
void build(int v, int l, int r) {
if(l == r) {
ST[v].push_back(P[l]);
return;
}
build(v * 2, l, (l + r) / 2);
build(v * 2 + 1, (l + r) / 2 + 1, r);
int i = 0, j = 0;
while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
if(i == ST[v * 2].size())
ST[v].push_back(ST[v * 2 + 1][j++]);
else if(j == ST[v * 2 + 1].size())
ST[v].push_back(ST[v * 2][i++]);
else {
if(ST[v * 2][i] < ST[v * 2 + 1][j])
ST[v].push_back(ST[v * 2][i++]);
else ST[v].push_back(ST[v * 2 + 1][j++]);
}
}
}
void buildM(int v, int l, int r) {
if(l == r) {
MX[v] = H[l];
return;
}
buildM(v * 2, l, (l + r) / 2);
buildM(v * 2 + 1, (l + r) / 2 + 1, r);
MX[v] = max(MX[v * 2], MX[v * 2 + 1]);
}
int query(int v, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return 0;
if(l >= lo && r <= hi) return MX[v];
return max(query(v * 2, l, (l + r) / 2, lo, hi),
query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
}
int queryR(int v, int l, int r, int lo, int hi, int K) {
if(l > hi || r < lo) return 1e9 + 7;
if(l >= lo && r <= hi) {
int rf = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin();
if(rf == ST[v].size()) return 1e9 + 7;
return ST[v][rf];
}
return min(queryR(v * 2, l, (l + r) / 2, lo, hi, K),
queryR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, K));
}
int queryL(int v, int l, int r, int lo, int hi, int K) {
if(l > hi || r < lo) return -1;
if(l >= lo && r <= hi) {
int lf = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin();
if(lf == 0) return -1;
return ST[v][--lf];
}
return max(queryL(v * 2, l, (l + r) / 2, lo, hi, K),
queryL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, K));
}
void init(int _N, vector<int> _H) {
N = _N;
for(int l = 0; l < _N; l++) {
H.push_back(_H[l]);
P[_H[l]] = l;
}
for(int l = 0; l < 20; l++) {
R[N + 1] = N + 1, L[N + 1] = N + 1, UP[N + 1][l] = DN[N + 1][l] = N + 1;
par[N + 1][l] = N + 1;
}
build(1, 1, N);
buildM(1, 0, N - 1);
for(int l = 0; l < _N; l++) {
int i = queryL(1, 1, N, _H[l] + 1, N, l);
int j = queryR(1, 1, N, _H[l] + 1, N, l);
L[l] = UP[l][0] = (i != -1 ? i : N + 1);
R[l] = DN[l][0] = (j != 1e9 + 7 ? j : N + 1);
par[l][0] = R[l];
if(_H[R[l]] < _H[L[l]])
swap(UP[l][0], DN[l][0]);
}
for(int l = 1; l < 20; l++)
for(int i = 0; i < _N; i++) {
UP[i][l] = UP[UP[i][l - 1]][l - 1];
DN[i][l] = DN[DN[i][l - 1]][l - 1];
par[i][l] = par[par[i][l - 1]][l - 1];
}
}
int solve(int U, int C, int D) {
int best = 0;
if(R[U] >= C && R[U] <= D) return 1;
for(int l = 19; l >= 0; l--)
if(R[UP[U][l]] < C) best += (1 << l), U = UP[U][l];
if(R[UP[U][0]] >= C && R[UP[U][0]] <= D) return 2 + best;
for(int l = 19; l >= 0; l--)
if(R[DN[U][l]] < C) best += (1 << l), U = DN[U][l];
if(R[DN[U][0]] >= C && R[DN[U][0]] <= D) return 2 + best;
if(DN[U][0] >= C && DN[U][0] <= D) return 1 + best;
return -1;
}
int minimum_jumps(int A, int B, int C, int D) {
int lo = A, hi = B, ans = -1;
int G = query(1, 0, N - 1, C, D);
while(lo <= hi) {
int md = (lo + hi) / 2;
int q = query(1, 0, N - 1, md, B);
if(q < G) ans = md, hi = md - 1;
else lo = md + 1;
}
if(ans == -1) return -1;
int U = query(1, 0, N - 1, ans, B); U = P[U];
int res = solve(U, C, D);
return (res > N ? -1 : res);
}
컴파일 시 표준 에러 (stderr) 메시지
jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
| ~~^~~~~~~~~~~~~~~~~~
jumps.cpp:24:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:25:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | if(i == ST[v * 2].size())
| ~~^~~~~~~~~~~~~~~~~~~
jumps.cpp:27:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | else if(j == ST[v * 2 + 1].size())
| ~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int queryR(int, int, int, int, int, int)':
jumps.cpp:58:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if(rf == ST[v].size()) return 1e9 + 7;
| ~~~^~~~~~~~~~~~~~~
# | 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... |