| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 692531 | gustjwkd1007 | Rainforest Jumps (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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)
ll mod(ll a, ll b) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
ll g = a; x = 1, y = 0;
if(b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
return g;
}
int inv[210000], dep[210000];
int sparse[2][210000][30];
vector <int> input, gan[210000];
int max_seg[810000];
int n;
int build(int s, int e, int ind){
if(s==e)
return max_seg[ind] = input[s];
int m = (s+e)/2;
return max_seg[ind] = max(build(s, m, ind*2), build(m+1, e, ind*2+1));
}
int rmq(int s, int e, int ind, int x, int y){
if(s>y||e<x)
return 0;
if(s>=x&&e<=y)
return max_seg[ind];
return max(
rmq(s, (s+e)/2, ind*2, x, y),
rmq((s+e)/2+1, e, ind*2+1, x, y)
);
}
int low_cd(int C, int D, int M){
int l = C, r = D;
while(l<=r){
int m = (l+r)/2;
if(rmq(1, n, 1, C, m)>M)
r = m-1;
else
l = m+1;
}
return l;
}
int low_ab(int A, int B, int M){
int l = A, r = B;
while(l<=r){
int m = (l+r)/2;
if(rmq(1, n, 1, m, B)<M)
r = m-1;
else
l = m+1;
}
return l-1;
}
int dist(int s, int e){
int re=0;
for(int i=29;i>=0;i--)if(dep[sparse[1][s][i]]>=dep[e]){
re += (1 << i);
s = sparse[1][s][i];
}
return re - dep[e] + dep[s];
}
void set_inv(){
for(int i=1;i<=n;i++)
inv[input[i]]=i;
}
void dfs(int now){
for(int t=0;t<2;t++){
for(int i=1;i<30;i++)
sparse[t][now][i] = sparse[t][sparse[t][now][i-1]][i-1];
}
for(int nex : gan[now]){
dep[nex] = dep[now]+1;
dfs(nex);
}
}
void set_sparse(){
stack <int> ms;
ms.push(0);
for(int i=1;i<=n;i++){
for(;input[ms.top()]<input[i];ms.pop());
sparse[0][i][0] = ms.top();
ms.push(i);
}
while(ms.size()) ms.pop();
ms.push(0);
for(int i=n;i>0;i--){
for(;input[ms.top()]<input[i];ms.pop());
sparse[1][i][0] = ms.top();
ms.push(i);
}
for(int i=1;i<=n;i++)if(input[sparse[0][i][0]]>input[sparse[1][i][0]])
swap(sparse[0][i][0], sparse[1][i][0]);
for(int i=1;i<=n;i++)
gan[sparse[0][i][0]].push_back(i);
dfs(0);
}
void init(int N, std::vector<int> H) {
input.push_back(INF);
input.insert(input.end(), H.begin(), H.end());
n=N;
set_inv();
set_sparse();
build(1, n, 1);
}
int minimum_jumps(int A, int B, int C, int D) {
A++, B++, C++, D++;
int M = rmq(1, n, 1, B+1, C-1);
int la = low_ab(1, B, M);
int lc = low_cd(C, D, M);
int MAB = rmq(1, n, 1, A, B);
int MCD = rmq(1, n, 1, C, D);
if(lc>D)
return -1;
if(la<A){
if(input[la]<MCD)
return min(dist(inv[MAB], lc), dist(inv[MAB], la) + 1);
return dist(inv[MAB], lc);
}
if(rmq(1, n, 1, C, D)>input[la])
return 1;
if(la==B)
return -1;
return dist(inv[rmq(1, n, 1, la+1, B)], lc);
}
int main() {
int N, Q;
assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i) {
int A, B, C, D;
assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
printf("%d\n", minimum_jumps(A, B, C, D));
}
return 0;
}