이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define MAX 500005
#define oo 1e18
#define pll pair<ll,ll>
#define F first
#define S second
const ll bts=20;
pll v[MAX],p[MAX],s[bts+10][MAX];
ll d[MAX],t[bts+10][MAX];
vll h;
void init(int n, std::vector<int> H) {
H.push_back(0);
queue<pair<ll,pll>> q;q.push({n,{0,n-1}});
d[n]=0;s[0][n]={n,n};
while(!q.empty()){
pair<ll,pll> u=q.front();q.pop();
pair<ll,pll> h1={-1,{u.S.F,u.F-1}};
pair<ll,pll> h2={-1,{u.F+1,u.S.S}};
pll mx1={0,n},mx2={0,n};
for(int i=h1.S.F;i<=h1.S.S;i++){
mx1=max(mx1,{H[i],i});
}
for(int i=h2.S.F;i<=h2.S.S;i++){
mx2=max(mx2,{H[i],i});
}
h1.F=mx1.S;h2.F=mx2.S;
v[u.F]={h1.F,h2.F};
if(h1.F!=n){
q.push(h1);
d[h1.F]=d[u.F]+1;
p[h1.F]={h1.S.F-1,h1.S.S+1};
s[0][h1.F].F=u.S.F-1;
s[0][h1.F].S=u.F;
}
if(h2.F!=n){
q.push(h2);
d[h2.F]=d[u.F]+1;
p[h2.F]={h2.S.F-1,h2.S.S+1};
s[0][h2.F].F=u.S.S+1;
s[0][h2.F].S=u.F;
}
}
for(int i=0;i<=n;i++){
if(s[0][i].F==-1)s[0][i].F=n;
if(s[0][i].S==-1)s[0][i].S=n;
//cout<<s[0][i].S<<" ";
}//cout<<"\n";
for(int i=1;i<=bts;i++){
for(int j=0;j<=n;j++){
s[i][j].F=s[i-1][s[i-1][j].F].F;
s[i][j].S=s[i-1][s[i-1][j].S].S;
// cout<<s[i][j].S<<" ";
}//cout<<"\n";
}
}
int minimum_jumps(int A, int B, int C, int D) {
swap(B,C);
//cout<<A<<" "<<B<<"\n";
if(A<=p[B].F)return -1;
//cout<<A<<" "<<B<<"\n";
ll r=0;
for(int i=bts;i>=0;i--){
//cout<<"s["<<i<<"]["<<A<<"]="<<s[i][A].S<<"\n";
if(d[s[i][A].F]>=d[B]){
r+=(1LL<<i);
A=s[i][A].F;
}
// cout<<i<<":"<<A<<" "<<B<<"\n";
}
for(int i=bts;i>=0;i--){
if(d[s[i][A].S]>=d[B]){
r+=(1LL<<i);
A=s[i][A].S;
// cout<<A<<" "<<B<<"\n";
}
}
return r;
}
# | 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... |