이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "jumps.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> mas;
const int dydis = 1e5 + 10;
const int dd = 20;
int mx[dydis][dd];
int lg2[dydis];
void build() {
lg2[1] = 0;
for(int i = 2; i < dydis; i++) lg2[i] = lg2[i/2] + 1;
for(int i = 0; i < n; i++) {
mx[i][0] = mas[i];
}
for(int j = 1; j < dd; j++) {
for(int i = 0; i < n; i++) {
int r = i + (1 << (j-1));
r = min(r, n-1);
mx[i][j] = max(mx[i][j-1], mx[r][j-1]);
}
}
}
vector<int> gr[dydis];
int h[dydis];
void dfs(int v) {
for(auto x : gr[v]) {
h[x] = h[v] + 1;
dfs(x);
}
}
int getMx(int a, int b) {
int pw = lg2[b - a + 1];
// cout << a << "; " << b << " issiskaido i intervala [" << a << "; " << a + (1 << pw) - 1 << "] ir intervala [" << b - (1 << pw) + 1 << "; " << b << "]\n";
int ind = b - (1 << pw) + 1;
return max(mx[a][pw], mx[ind][pw]);
}
int firstLarger[dydis];
void init(int N, vector<int> H) {
n = N ;
mas = H;
build();
set<pair<int, int> > setas;
for(int i = 0; i < n; i++) {
firstLarger[i] = -1;
while(setas.size()) {
if(mas[i] > setas.begin()->first) {
firstLarger[setas.begin()->second] = i;
setas.erase(*setas.begin());
}else break;
}
setas.insert({mas[i], i});
}
vector<int> roots;
for(int i = 0; i < n; i++) {
if(firstLarger[i] == -1) {
roots.push_back(i);
}else {
gr[firstLarger[i]].push_back(i);
}
}
for(auto x : roots) {
h[x] = 0;
dfs(x);
}
}
bool arGalima(int a, int b) { /// ar galima is a i b?
if(mas[a] >= mas[b]) return false;
if(a == b-1) return true;
if(getMx(a+1, b-1) < b) return true;
return false;
}
int minimum_jumps(int A, int B, int C, int D) {
// cout << "maximumas tarp " << A << " ir " << C << " yra " << getMx(A, C) << endl;
if(arGalima(A, C) == false) return -1;
return h[A] - h[C];
}
# | 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... |