#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBITe
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 1e5+5;
int n,k,q;
int bst[21][maxn][2];
int a[maxn];
int s[maxn];
ll QU(int e) {
ll re = 0;
for (++e; e>0; e-=e&-e) re += s[e];
return re;
}
void MO(int e, int v) {
for (++e; e<maxn; e+=e&-e) s[e] += v;
}
int seg[2 * maxn];
void build() { // build the tree
for (int i = maxn - 1; i > 0; --i) seg[i] = max(seg[i<<1] , seg[i<<1|1]);
}
void modify(int p, int value) { // set value at position p
for (seg[p += maxn] = value; p > 1; p >>= 1) seg[p>>1] = max(seg[p] , seg[p^1]);
}
int query(int l, int r) { // sum on interval [l, r)
int res = 0;
for (l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
if (l&1) res = max(res, seg[l++]);
if (r&1) res = max(res, seg[--r]);
}
return res;
}
struct qq{
int x,y,mx,id;
};
int leq(vector<int> & x, int a) {
return upper_bound(ALL(x), a) - x.begin();
}
int to[maxn][2];
void walk(array<int, 2> &A) {
A[0] = bst[0][A[0]][0];
A[1] = bst[0][A[1]][1];
if (a[A[0]] != a[A[1]]) {
if (a[A[0]] > a[A[1]]) A[1] = A[0];
else A[0] = A[1];
}
}
void ass(bool x) {if (!x) while(1); }
signed main(){
IOS();
// cout<<"1\n3\n0\n"; return 0;
cin>>n>>k>>q;
// assert(n<=25);
for (int i = 0; i<n; ++i) {
cin>>a[i];
modify(i,a[i]);
}
// build();
bug(query(0,3));
vector<int> ps = {0};
for (int i = 0; i<n; ++i) {
while (a[ps.back()] < a[i]) {
ps.pop_back();
}
bst[0][i][0] = ps.back();
ps.pb(i);
}
ps = {n-1};
for (int i = n-1; i>=0; --i) {
while (a[ps.back()] < a[i]) {
ps.pop_back();
}
bst[0][i][1] = ps.back();
ps.pb(i);
}
for (int i = 0; i<n; ++i) {
to[i][0] = bst[0][i][0];
to[i][1] = bst[0][i][1];
// tie(to[i][0], to[i][1]) = make_pair(bst[0][i][0], bst[0][i][1]);
if (a[bst[0][i][0]] != a[bst[0][i][1]]) {
if (a[bst[0][i][0]] < a[bst[0][i][1]]) {
bst[0][i][0] = bst[0][i][1];
}else{
bst[0][i][1] = bst[0][i][0];
}
}
bug(bst[0][i][0], bst[0][i][1]);
}
for (int j = 1; j<21; ++j) {
for (int i = 0; i<n; ++i) {
// vector<int> tv = {}
int bt = -1;
int L = 0, R = 0;
for (int a1 = 0; a1<2; ++a1) for (int a2 = 0; a2<2; ++a2) {
int it = bst[j-1][bst[j-1][i][a1]][a2];
if (a[it] > bt) {
L = R = it; bt = a[it];
}
if (a[it] == bt) {
L = min(L, it); R = max(R, it);
}
// MX(bst, )
}
bst[j][i][0] = L;
bst[j][i][1] = R;
if (a[bst[j][i][0]] != a[bst[j][i][1]]) if (a[bst[j][i][0]] < a[bst[j][i][1]]) {
bst[j][i][0] = bst[j][i][1];
}else{
bst[j][i][1] = bst[j][i][0];
}
if (j == 2) {
array<int,2> tmp = {{bst[j][i][0], bst[j][i][1]}};
array<int,2> t2 = {{i,i}}; walk(t2); walk(t2); walk(t2); walk(t2);
assert(tmp == t2);
}
}
}
vector<qq > ques;
for (int cnt = 0; cnt < q; ++cnt) {
int x,y; cin>>x>>y; --x; --y;
if (x > y) swap(x,y);
ques.pb({x,y,query(x,y + 1), cnt});
}
// sort(ALL(ques), [&](qq A, qq b){return A.mx > b.mx;});
vector<vector<int> > upd (k+1);
for (int i = 0; i<n; ++i) {
upd[a[i]].pb(i);
}
int tmp = k+1;
vector<int> ans(q,100000000);
vector<qq> resv;
for (int cnt = 0; cnt<q; ++cnt) {
int x = ques[cnt].x, y = ques[cnt].y;
assert(x!=y);
int mx = ques[cnt].mx;
int id = ques[cnt].id;
// if (id != 3) continue;
// x is lower
bug(x+1,y+1,mx,id);
for (int df = 0; df < 2; ++df) {
if (df>0 && mx == k) break;
array<int, 2> T = {{x,y}};
int steps = 0;
for (int &X : T) {
int dir = X<y;
array<int, 2> at = {{X,X}};
// for (int j = 20; j>=0; --j) {
// array<int, 2> at2 = {{bst[j][at[0]][0],bst[j][at[1]][1]}};
// if (a[at2[0]] != a[at2[1]]) {
// if (a[at2[0]] > a[at2[1]]) at2[1] = at2[0];
// else at2[0] = at2[1];
// }
// if (a[at2[0]] < mx + df) {
// steps += (1<<j);
//// bug(j, bst[j][X][dir], bst[j][X][dir^1]);
////// X = bst[j][X][dir];
// at = at2;
// }
// }
while (1) {
array<int, 2> at2 = at; walk(at2);
if (a[at2[0]] < mx+df) {
// assert(0);
steps++; at=at2;
}else break;
}
X=at[dir];
bug(steps, X, y);
bug(a[X], mx + df, mx, df);
if (a[X] >= mx+df) --steps;
else {
if (df == 0) {
if (a[to[X][dir]] >= mx) X = to[X][dir];
else X = bst[0][X][dir];
if (a[X] < mx) {
X = at[dir^1];
if (a[to[X][dir]] >= mx) X = to[X][dir^1];
else {
X = bst[0][X][dir];
if (a[X] < mx) X=bst[0][X][dir^1];
ass(a[X] >= mx);
}
}
}else{
walk(at);
if (a[at[dir]] >= mx+df) {
X = at[dir];
}else{
X = at[dir^1];
assert(a[X] >= mx + df);
}
}
}
}
// assert(T[0]<=T[1]);
int smol = min(a[T[0]], a[T[1]]);
if (df == 0)
assert(smol >= mx + df);
// if (smol < mx + df) continue;
bug(smol, mx);
bug(steps, smol);
MN(ans[id] , (a[T[0]] != a[T[1]]) + steps + (T[0] <= T[1]?leq(upd[smol], T[1]) - leq(upd[smol], T[0]-1) : 0));
// resv.pb(T[0], T[1], , cnt) ;
}
// bug(nxt, y);
}
// for (int cnt = 0; cnt < q; ++cnt) {
// while (tmp > a[y]) {
// --tmp;
// bug(tmp, y, a[y]);
// for (int w : upd[tmp]) {
// MO(w,1);
// }
// }
// }
for (int i = 0; i<q; ++i) {
cout<<ans[i]<<endl;
}
}
/*
9 3 1
3 1 1 2 2 1 1 1 3
2 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
0 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
43 ms |
19448 KB |
Output is correct |
| 3 |
Correct |
44 ms |
19448 KB |
Output is correct |
| 4 |
Correct |
53 ms |
19192 KB |
Output is correct |
| 5 |
Correct |
43 ms |
19320 KB |
Output is correct |
| 6 |
Correct |
45 ms |
19320 KB |
Output is correct |
| 7 |
Correct |
54 ms |
23160 KB |
Output is correct |
| 8 |
Correct |
52 ms |
22220 KB |
Output is correct |
| 9 |
Correct |
58 ms |
22268 KB |
Output is correct |
| 10 |
Correct |
48 ms |
20336 KB |
Output is correct |
| 11 |
Correct |
54 ms |
22392 KB |
Output is correct |
| 12 |
Correct |
51 ms |
20728 KB |
Output is correct |
| 13 |
Correct |
50 ms |
20216 KB |
Output is correct |
| 14 |
Correct |
52 ms |
22392 KB |
Output is correct |
| 15 |
Correct |
52 ms |
20728 KB |
Output is correct |
| 16 |
Correct |
53 ms |
20212 KB |
Output is correct |
| 17 |
Correct |
46 ms |
21624 KB |
Output is correct |
| 18 |
Correct |
46 ms |
21624 KB |
Output is correct |
| 19 |
Correct |
51 ms |
23928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
21776 KB |
Output is correct |
| 2 |
Correct |
125 ms |
21988 KB |
Output is correct |
| 3 |
Correct |
121 ms |
21768 KB |
Output is correct |
| 4 |
Correct |
119 ms |
21768 KB |
Output is correct |
| 5 |
Correct |
121 ms |
21896 KB |
Output is correct |
| 6 |
Correct |
124 ms |
21868 KB |
Output is correct |
| 7 |
Correct |
122 ms |
21896 KB |
Output is correct |
| 8 |
Correct |
121 ms |
22248 KB |
Output is correct |
| 9 |
Execution timed out |
2083 ms |
21612 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
25320 KB |
Output is correct |
| 2 |
Correct |
128 ms |
25448 KB |
Output is correct |
| 3 |
Correct |
116 ms |
21992 KB |
Output is correct |
| 4 |
Correct |
118 ms |
22768 KB |
Output is correct |
| 5 |
Execution timed out |
2086 ms |
24044 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
