이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define pb push_back
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_io freopen("input.in" , "r" , stdin) ; freopen("output.out" , "w" , stdout);
using namespace std;
typedef long long ll;
typedef long double dll;
const int N = 2e5+7, lg = 23, inf = 1e9;
vector<int> g[N],vec;
int dist[N], n, hi[N], seg[N<<2], sm[lg][N], big[lg][N], l[N], r[N];
bool sub1 = false;
queue<int> q;
//#include "jumps.h"
void build(int ind = 1, int l = 0, int r = n-1){
if (l == r){
seg[ind] = hi[l];
return;
}
int mid = (l+r)>>1;
build(2*ind,l,mid);
build(2*ind+1,mid+1,r);
seg[ind] = max(seg[2*ind],seg[2*ind+1]);
}
int get(int st, int en, int ind = 1, int l = 0, int r = n-1){
if (l > en || st > r) return 0;
if (l == r || (l >= st && r <= en)) return seg[ind];
int mid = (l+r)>>1;
return max(get(st,en,2*ind,l,mid),get(st,en,2*ind+1,mid+1,r));
}
void init(int _n, vector<int> h){
n = _n;
for(int i=0; i<n; i++) hi[i] = h[i];
sub1 = true;
for(int i=0; i<n; i++) if (h[i] != i+1) sub1 = false;
vec.pb(0);
l[0] = -1;
for(int i=0; i<n; i++){
while(vec.size() && h[vec.back()] < h[i]) vec.pop_back();
if (vec.size()){
g[i].pb(vec.back());
l[i] = vec.back();
}
else l[i] = -1;
vec.pb(i);
}
vec.clear();
vec.pb(n-1);
r[n-1] = -1;
for(int i=n-2; i>=0; i--){
while(vec.size() && h[vec.back()] < h[i]) vec.pop_back();
if (vec.size()){
g[i].pb(vec.back());
r[i] = vec.back();
}
else r[i] = -1;
vec.pb(i);
}
build();
for(int j=0; j<lg; j++) for(int i=0; i<n; i++) big[j][i] = sm[j][i] = -1;
for(int i=0; i<n; i++){
if (l[i] != -1) big[0][i] = l[i];
if (r[i] != -1){
if (big[0][i] == -1 || h[big[0][i]] < h[r[i]]){
sm[0][i] = big[0][i];
big[0][i] = r[i];
}
else sm[0][i] = r[i];
}
}
for(int j=1; j<lg; j++){
for(int i=0; i<n; i++){
if (big[j-1][i] != -1) big[j][i] = big[j-1][big[j-1][i]];
if (sm[j-1][i] != -1) sm[j][i] = sm[j-1][sm[j-1][i]];
}
}
}
int sub56(int st, int en){
if (hi[st] > hi[en] || get(st+1,en-1) > hi[en]) return -1;
int ans = 0;
int v = st;
for(int i=lg-1; i>=0; i--){
if (big[i][v] != -1 && hi[big[i][v]] <= hi[en]){
v = big[i][v];
ans += (1<<i);
}
}
for(int i=lg-1; i>=0; i--){
if (sm[i][v] != -1 && hi[sm[i][v]] <= hi[en]){
v = sm[i][v];
ans += (1<<i);
}
}
return ans;
}
int minimum_jumps(int a, int b, int c, int d){
if (sub1) return c-b;
if (c == d){
int ind = -1;
for(int i=b; i>=a; i--){
if (hi[i] < hi[c] && (ind == -1 || (ind != -1 && hi[i] > hi[ind]))) ind = i;
}
if (ind == -1) return -1;
return sub56(ind,c);
}
return -1;
fill(dist,dist+n,inf);
for(int i=a; i<=b; i++){
dist[i] = 0;
q.push(i);
}
while(q.size()){
int v = q.front(); q.pop();
for(int u : g[v]){
if (dist[u] > dist[v] + 1){
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
int mn = inf;
for(int i=c; i<=d; i++) mn = min(mn,dist[i]);
return (mn == inf ? -1 : mn);
}
/*
int32_t main(){
fast_io;
vector<int> tmp = {3, 2, 1, 6, 4, 5, 7};
init(7, tmp);
cout << minimum_jumps(4, 4, 6, 6) << endl;
cout << minimum_jumps(0, 1, 2, 2) << endl;
return 0;
}
*/
# | 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... |