// author : sentheta aka vanwij
#ifdef VANWIJ
#include"/home/user/code/bits/stdc++.h"
#define DBG 0
#else
#include"bits/stdc++.h"
#define DBG 0
#endif
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}
#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
Int ret = 1;
for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}
void solve(); int TC, ALLTC;
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
solve();
}
const int N = 1e5+5;
const int LN = 17;
int n, k, q;
int a[N];
V<int> bya[N];
struct Stable{
int st[N][LN];
void build(){
rep(i,0,N) st[i][0] = a[i];
rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<N; i++){
st[i][lg] = max(st[i][lg-1], st[i+(1<<(lg-1))][lg-1]);
}
}
int qry(int l,int r){
int lg = __lg(r-l+1);
return max(st[l][lg], st[r-(1<<lg)+1][lg]);
}
} stable;
V<int> adj[N];
int prv[N][LN], nxt[N][LN];
// p[i][k] = maximum value after 2^k moves, leftmost and rightmost position
int pl[N][LN], pr[N][LN];
void solve1(){
int s, t;
cin >> s >> t;
// wlog s < t
if(!(s<t)) swap(s,t);
if(s==t-1){
cout << 0 << nl; return;
}
int ans = N;
dbg(s); dbg(t);
int barrier = stable.qry(s+1,t-1);
dbg(barrier);
int sl=s, sr=s;
int tl=t, tr=t;
int dist = 0;
for(int b=LN-1; b>=0; b--){
if(a[pl[sl][b]] < barrier){
sl = pl[sl][b]; sr = pr[sr][b];
dist += 1<<b;
}
if(a[pl[tl][b]] < barrier){
tl = pl[tl][b]; tr = pr[tr][b];
dist += 1<<b;
}
}
dbg(sl); dbg(sr); dbg(tl); dbg(tr);
assert(sr < tl);
V<int> vs = {
s, prv[sl][0], nxt[sr][0]
};
V<int> vt = {
t, prv[tl][0], nxt[tr][0]
};
dbg(dist);
for(int x : vs) cerr << x << " ";
cerr << nl;
for(int y : vt) cerr << y << " ";
cerr << nl;
for(int ox : vs) if(a[ox] >= barrier)
for(int oy : vt) if(a[oy] >= barrier){
cerr << nl;
int x=ox, y=oy;
dbg(x);
dbg(y);
int dist2 = dist;
if(x!=s) dist2++;
if(y!=t) dist2++;
dbg(dist2);
// x move right to y
if(a[x] <= a[y]){
for(int b=LN-1; b>=0; b--){
if(nxt[x][b] < y){
x = nxt[x][b];
dist2 += 1<<b;
}
}
if(x!=y) dist2++;
}
// y move left to x
else{
for(int b=LN-1; b>=0; b--){
if(x < prv[y][b]){
y = prv[y][b];
dist2 += 1<<b;
}
}
if(x!=y) dist2++;
}
ans = min(ans, dist2);
dbg(dist2);
}
cout << ans-1 << nl;
}
void solve(){
cin >> n >> k >> q;
rep(i,1,n+1){
cin >> a[i];
bya[a[i]].push_back(i);
}
stable.build();
// toward-left edges
V<int> stak;
rep(i,1,n+1){
while(!stak.empty() && a[stak.back()]<a[i]) stak.pop_back();
if(stak.empty()) stak.push_back(i);
int j = stak.back();
prv[i][0] = j;
if(stak.back()!=i) stak.push_back(i);
}
// toward-right edges
stak.clear();
for(int i=n; i>=1; i--){
while(!stak.empty() && a[stak.back()]<a[i]) stak.pop_back();
if(stak.empty()) stak.push_back(i);
int j = stak.back();
nxt[i][0] = j;
if(stak.back()!=i) stak.push_back(i);
}
// build p[][]
rep(i,1,n+1){
int mx = max({
a[prv[i][0]], a[nxt[i][0]]
});
pl[i][0] = N;
pr[i][0] = 0;
if(a[prv[i][0]]==mx){
pl[i][0] = min(pl[i][0], prv[i][0]);
pr[i][0] = max(pr[i][0], prv[i][0]);
}
if(a[nxt[i][0]]==mx){
pl[i][0] = min(pl[i][0], nxt[i][0]);
pr[i][0] = max(pr[i][0], nxt[i][0]);
}
dbg(i);
dbg(nxt[i][0]);
dbg(prv[i][0]);
dbg(pl[i][0]);
dbg(pr[i][0]);
cerr << nl;
}
rep(lg,1,LN) rep(i,1,n+1){
prv[i][lg] = prv[prv[i][lg-1]][lg-1];
nxt[i][lg] = nxt[nxt[i][lg-1]][lg-1];
V<int> v = {
pl[pl[i][lg-1]][lg-1], pl[pr[i][lg-1]][lg-1],
pr[pl[i][lg-1]][lg-1], pr[pr[i][lg-1]][lg-1]
};
int mx = 0;
for(int j : v) mx = max(mx, a[j]);
pl[i][lg] = N;
pr[i][lg] = 0;
for(int j : v) if(a[j]==mx){
pl[i][lg] = min(pl[i][lg], j);
pr[i][lg] = max(pr[i][lg], j);
}
}
while(q--){
solve1();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
18388 KB |
Output is correct |
| 2 |
Correct |
13 ms |
18388 KB |
Output is correct |
| 3 |
Correct |
12 ms |
18352 KB |
Output is correct |
| 4 |
Correct |
14 ms |
18348 KB |
Output is correct |
| 5 |
Incorrect |
15 ms |
18388 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
18884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
237 ms |
75228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
203 ms |
76388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
