| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1052601 | kachim2 | 밀림 점프 (APIO21_jumps) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "jumps.h"
#include "stub.cpp"
#include<queue>
#include<array>
#include <vector>
#include <iostream>
using namespace std;
std::vector<int> H;
vector<int> nxt;
vector<int> prv;
vector<int> d;
array<pair<int, int>, 1<<5> segtree;
vector<array<int, 25>> jp;
vector<array<int, 25>> njp;
bool subtask1=1;
pair<int, int> mquery(int a, int b){
a--;
b++;
a+=(segtree.size()/2)+1;
b+=(segtree.size()/2)+1;
pair<int, int> res = {0, 0};
while(b-a > 1){
if(a%2 == 0){
res = max(segtree[a+1], res);
}
if(b%2 == 1){
res = max(segtree[b-1], res);
}
a/=2;
b/=2;
}
return res;
}
void init(int N, std::vector<int> nH)
{
for(int i = 0; i < N; i++){
if(nH[i]!=i+1) subtask1=0;
}
H = nH;
nxt.resize(N);
prv.resize(N);
jp.resize(N);
njp.resize(N);
{
vector<int> kmon;
for (int i = 0; i < N; i++)
{
if (kmon.empty())
{
kmon.push_back(i);
prv[i] = -1;
continue;
}
while (H[kmon.back()] < H[i])
{
kmon.pop_back();
if (kmon.empty())
{
kmon.push_back(i);
prv[i] = -1;
goto nd;
}
}
prv[i] = kmon.back();
kmon.push_back(i);
nd:;
}
}
{
vector<int> kmon;
for (int i = N-1; i>=0; i--)
{
if (kmon.empty())
{
kmon.push_back(i);
nxt[i] = -1;
continue;
}
while (H[kmon.back()] < H[i])
{
kmon.pop_back();
if (kmon.empty())
{
kmon.push_back(i);
nxt[i] = -1;
goto nd2;
}
}
nxt[i] = kmon.back();
kmon.push_back(i);
nd2:;
}
}
for(int i = 0; i < N; i++){
if(H[prv[i]]>H[nxt[i]]){
jp[i][0] = prv[i];
}else if (H[prv[i]]<H[nxt[i]]){
jp[i][0] = nxt[i];
}else{
jp[i][0] = -1;
}
}
for(int j = 1; j < jp[0].size(); j++){
for(int i = 0; i < N; i++){
if(jp[i][j-1] != -1)
jp[i][j] = jp[jp[i][j-1]][j-1];
else jp[i][j] = -1;
}
}
for(int i = 0; i < N; i++){
njp[i][0] = nxt[i];
}
for(int j = 1; j < njp[0].size(); j++){
for(int i = 0; i < N; i++){
if(njp[i][j-1] != -1)
njp[i][j] = njp[njp[i][j-1]][j-1];
else njp[i][j] = -1;
}
}
for(int i = 0; i < N; i++){
segtree[i+(segtree.size()/2)+1].first = H[i];
segtree[i+(segtree.size()/2)+1].second = i;
}
for(int i = segtree.size()/2-1; i>=1; i--){
segtree[i] = max(segtree[i*2], segtree[i*2+1]);
}
}
int minimum_jumps(int A, int B, int C, int D)
{
if (subtask1) return C-B;
if( C==D){
int cur = -1;
if(H[B]> H[C]) return -1;
{
int l = A, r = B;
while(l<=r){
const int mid = (l+r)/2;
int x = mquery(mid, B).first;
if(x>H[C]){
l = mid+1;
}else{
r = mid-1;
cur = mid;
}
}
if(cur == -1) return -1;
cur = mquery(cur, B).second;
}
if(cur == -1) return -1;
int res=0;
for(int i = jp[0].size()-1; i>=0; i--){
if(jp[cur][i]!=-1){
if(H[jp[cur][i]] <= H[C]){
res+=1<<i;
if(jp[cur][i] == C) return res;
cur = jp[cur][i];
}
}
}
for(int i = njp[0].size()-1; i>=0; i--){
if(njp[cur][i]!=-1){
if(njp[cur][i] <= C){
res+=1<<i;
if(njp[cur][i] == C) return res;
cur = njp[cur][i];
}
}
}
return -1;
}
int mcd = 0;
for (int i = C; i <= D; i++)
{
mcd = max(mcd, H[i]);
}
int bs = 0;
for (int i = B; i >= A; i--)
{
// cerr << H[i] << ' ';
if (H[i] < mcd)
bs = max(bs, i);
else
break;
}
// cerr << bs << '\n';
vector<bool> visited(H.size(), 0);
queue<pair<int, int>> q;
for(int i = A; i <=B; i++)
q.push({i, 0});
while(!q.empty()){
auto x = q.front();
q.pop();
if(visited[x.first]) continue;
visited[x.first] = 1;
if(x.first >= C && x.first <= D) return x.second;
if(nxt[x.first]!=-1) q.push({nxt[x.first], x.second+1});
if(prv[x.first]!=-1) q.push({prv[x.first], x.second+1});
}
return -1;
}