#include <bits/stdc++.h>
using namespace std;
#define d1 array<int, 2>
#define d2 array<d1, 2>
const int mxN=1e5, mxM=3*mxN-4;
int n, k, q, l[mxN], ln1[mxN], ln2[mxN], ld[mxN], rn1[mxN], rn2[mxN], rd[mxN], m, d[mxM], x[mxM];
d1 p[mxN];
d2 anc[mxM][17];
unordered_map<int, int> mp[mxN];
d2 cmb(d2 a, d2 b, d2 c) {
if(b[0][1]==-1)
return b;
if(c[0][1]==-1)
return c;
if(!b[1][0])
b[1][0]=n;
if(!c[0][0])
c[0][0]=n;
d2 r={min(d1{b[0][0]+a[0][0], b[0][1]}, d1{c[0][0]+a[1][0], c[0][1]}), min(d1{b[1][0]+a[0][0], b[1][1]}, d1{c[1][0]+a[1][0], c[1][1]})};
return r;
}
int bld(int i, int j) {
if(mp[i].find(j)!=mp[i].end())
return mp[i][j];
int u=mp[i][j]=m++;
x[u]=i;
//cout << "node " << u << " " << i << " " << j << endl;
if(j<k) {
int nl, nr;
if(j>=l[i]) {
nl=bld(ln1[i], min(l[ln1[i]], l[rn1[i]]));
nr=bld(rn1[i], min(l[ln1[i]], l[rn1[i]]));
} else
nl=nr=(++mp[i].find(j))->second;
//cout << "n " << nl << " " << nr << endl;
anc[u][0]={{{ld[i]-ld[x[nl]], nl}, {rd[i]-rd[x[nr]], nr}}};
anc[u][0][0][0]=min(anc[u][0][1][0]+1, anc[u][0][0][0]);
anc[u][0][1][0]=min(anc[u][0][0][0]+1, anc[u][0][1][0]);
d[u]=d[anc[u][0][0][1]]+1;
} else
anc[u][0][0][1]=-1;
for(int k=1; k<17; ++k)
anc[u][k]=~anc[u][k-1][0][1]?cmb(anc[u][k-1], anc[anc[u][k-1][0][1]][k-1], anc[anc[u][k-1][1][1]][k-1]):anc[u][k-1];
return u;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k >> q;
for(int i=0; i<n; ++i)
cin >> l[i];
for(int i=0; i<n; ++i) {
ln1[i]=ln2[i]=i-1;
while(~ln1[i]&&l[ln1[i]]<=l[i])
ln1[i]=ln1[ln1[i]];
while(~ln2[i]&&l[ln2[i]]<l[i])
ln2[i]=ln2[ln2[i]];
if(~ln2[i])
ld[i]=ld[ln2[i]]+1;
}
for(int i=n-1; ~i; --i) {
rn1[i]=rn2[i]=i+1;
while(rn1[i]<n&&l[rn1[i]]<=l[i])
rn1[i]=rn1[rn1[i]];
while(rn2[i]<n&&l[rn2[i]]<l[i])
rn2[i]=rn2[rn2[i]];
if(rn2[i]<n)
rd[i]=rd[rn2[i]]+1;
p[i]={l[i], i};
}
sort(p, p+n);
for(int i=n-1; ~i; --i)
bld(p[i][1], p[i][0]);
//auto dbg=[](d2 a) {
//cout << a[0][0] << " " << a[0][1] << " " << a[1][0] << " " << a[1][1] << endl;
//};
for(int a, b, ans; q--; ) {
cin >> a >> b, --a, --b;
a=mp[a][l[a]];
b=mp[b][l[b]];
if(d[a]<d[b])
swap(a, b);
d2 da{{{0, a}, {0, a}}}, db{{{0, b}, {0, b}}};
for(int i=16; ~i; --i)
if(d[da[0][1]]-(1<<i)>=d[b])
da=cmb(da, anc[da[0][1]][i], anc[da[1][1]][i]);
//dbg(da);
if(da[0][1]^b&&da[1][1]^b) {
for(int i=16; ~i; --i) {
d2 na=cmb(da, anc[da[0][1]][i], anc[da[1][1]][i]), nb=cmb(db, anc[db[0][1]][i], anc[db[1][1]][i]);
if(na[0][1]^nb[0][1]) {
da=na;
db=nb;
}
}
if(x[da[0][1]]>x[db[0][1]])
swap(da, db);
ans=da[1][0]+db[0][0]+ld[x[db[0][1]]]-ld[x[da[1][1]]];
da=cmb(da, anc[da[0][1]][0], anc[da[1][1]][0]), db=cmb(db, anc[db[0][1]][0], anc[db[1][1]][0]);
if(~da[0][1])
ans=min(da[0][0]+db[1][0]+1, ans);
} else if(da[0][1]^b)
ans=da[1][0];
else
ans=da[0][0];
cout << ans-1 << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
380 ms |
61252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
500 ms |
74792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
