제출 #1234406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234406		CELD_07	밀림 점프 (APIO21_jumps)	C++20	0 / 100	0 ms	408 KiB

jumps

#include "jumps.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
inline ll size(vector<ll>& a){
return a.size();
}
vector<ll> v, v1, v2;
vector<vector<ll>> t;
vector<vector<ll>> up, up1;
inline void build(ll v, ll tl ,ll tr){
if(tl==tr){
t[v].push_back(v2[tl]);
return;
}
ll tm=(tl+tr)/2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
t[v].resize(size(t[v*2]), size(t[v*2+1]));
merge(all(t[v*2]), all(t[v*2+1]), t[v].begin());
}
inline ll query(ll v, ll tl, ll tr, ll l, ll r, ll x){
if(tl>r || tr<l)return LLONG_MIN;
if(tl>=l && tr<=r){
auto it=upper_bound(all(t[v]), x);
if(it==t[v].begin())return LLONG_MIN;
it--;
return (*it);
}
ll tm=(tl+tr)/2;
return max(query(v*2, tl, tm, l, r, x), query(v*2+1, tm+1, tr, l, r, x));
}
ll n;
void init(int N, vector<int> H) {
n=N;
vector<ll>().swap(v);
vector<ll>().swap(v1);
vector<vector<ll>>().swap(up);
vector<vector<ll>>().swap(up1);
vector<vector<ll>>().swap(t);
vector<ll>().swap(v2);
t.resize(4*N);
up.assign(N+1, vector<ll>(23, -1));
up1.assign(N+1, vector<ll>(23, -1));
stack<pair<ll, ll>> s;
v.assign(N, -1);
v1.assign(N, -1);
for(int i=0; i<N; i++)v2.push_back(H[i]);
build(1, 0, N-1);
for(int i=N-1; i>=0; i--){
while(!s.empty() && s.top().ft<H[i])s.pop();
if(!s.empty())v[i]=s.top().sd;
s.push({H[i], i});
}
stack<pair<ll, ll>>().swap(s);
for(int i=0; i<N; i++){
while(!s.empty() && s.top().ft<H[i])s.pop();
if(!s.empty())v1[i]=s.top().sd;
s.push({H[i], i});
}
for(int i=0; i<N; i++){
if(v[i]==-1)up[i][0]=up1[i][0]=v1[i];
else if(v1[i]==-1)up[i][0]=up1[i][0]=v[i];
else{
if(max(v2[v[i]], v2[v1[i]])==v2[v[i]]){
up[i][0]=v[i];
up1[i][0]=v1[i];
}else{
up[i][0]=v1[i];
up1[i][0]=v[i];
}
}
}
for(int i=1; i<23; i++){
for(int j=0; j<N; j++){
if(up[j][i-1]!=-1)up[j][i]=up[up[j][i-1]][i-1];
if(up1[j][i-1]!=-1)up1[j][i]=up1[up1[j][i-1]][i-1];
}
}
//for(int i=0; i<N; i++)cout<<i<<" "<<v[i]<<" "<<v1[i]<<endl;
}

int minimum_jumps(int A, int B, int C, int D) {
    ll cnt=0;
    ll o=query(1, 0, n-1, A, B, v2[C]);
    if(o<A || o>B)return -1;
    for(int i=22; i>=0; i--){
    if(up[o][i]!=-1 && v2[up[o][i]]<=v2[C]){
    cnt+=(1LL<<i);
    o=up[o][i];
    }
    }
    for(int i=22; i>=0; i--){
    if(up1[o][i]!=-1 && v2[up1[o][i]]<=v2[C]){
    cnt+=(1LL<<i);
    o=up1[o][i];
    }
    }
    if(o==C)return cnt;
    else return -1;
}/*
int main(){
init(7, {3, 2, 1, 6, 4, 5, 7});
cout<<minimum_jumps(4, 4, 6, 6)<<endl;
}
*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19