// 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(sl!=pl[sl][b] && sr!=pr[sr][b] && a[pl[sl][b]]<barrier){
sl = pl[sl][b]; sr = pr[sr][b];
dist += 1<<b;
}
if(tl!=pl[tl][b] && tr!=pr[tr][b] && 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);
int dsl=1, dsr=1, dtl=1, dtr=1;
for(int b=LN-1; b>=0; b--){
if(a[prv[sl][b]]<barrier) sl=prv[sl][b], dsl+=1<<b;
if(a[nxt[sr][b]]<barrier) sr=nxt[sr][b], dsr+=1<<b;
if(a[prv[tl][b]]<barrier) tl=prv[tl][b], dtl+=1<<b;
if(a[nxt[tr][b]]<barrier) tr=nxt[tr][b], dtr+=1<<b;
}
sl=prv[sl][0];
sr=nxt[sr][0];
tl=prv[tl][0];
tr=nxt[tr][0];
V<pii> vs = {
{s,0}, {sl,dsl}, {sr,dsr}
};
V<pii> vt = {
{t,0}, {tl,dtl}, {tr,dtr}
};
dbg(dist);
for(auto[ox,dx] : vs) cerr << ox << " ";
cerr << nl;
for(auto[oy,dy] : vt) cerr << oy << " ";
cerr << nl;
for(auto[ox,dx] : vs) if(a[ox] >= barrier)
for(auto[oy,dy] : vt) if(a[oy] >= barrier){
cerr << nl;
int x=ox, y=oy;
dbg(x); dbg(y);
int dist2 = dist + dx + dy;
// if(x!=s) dist2++;
// if(y!=t) dist2++;
dbg(dist2);
// move x to y
if(a[x] <= a[y]){
if(x < y){
for(int b=LN-1; b>=0; b--){
if(nxt[x][b] < y){
x = nxt[x][b];
dist2 += 1<<b;
}
}
}
else if(y < x){
for(int b=LN-1; b>=0; b--){
if(y < prv[x][b]){
x = prv[x][b];
dist2 += 1<<b;
}
}
}
if(x!=y){
dist2++;
if(x < y) x = nxt[x][0];
else x = prv[x][0];
}
}
// y move left to x
else{
if(x < y){
for(int b=LN-1; b>=0; b--){
if(x < prv[y][b]){
y = prv[y][b];
dist2 += 1<<b;
}
}
}
else if(y < x){
for(int b=LN-1; b>=0; b--){
if(nxt[y][b] < x){
y = nxt[y][b];
dist2 += 1<<b;
}
}
}
if(x!=y){
dist2++;
if(x < y) y = prv[y][0];
else y = nxt[y][0];
}
}
assert(x==y);
ans = min(ans, dist2);
dbg(dist2);
}
assert(ans < N);
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 |
15 ms |
18344 KB |
Output is correct |
| 3 |
Correct |
13 ms |
18408 KB |
Output is correct |
| 4 |
Correct |
12 ms |
18312 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
18308 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
18920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
281 ms |
73836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
198 ms |
74644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
