#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) {
bst[j][i][0] = bst[j-1][bst[j-1][i][0]][0];
bst[j][i][1] = bst[j-1][bst[j-1][i][1]][1];
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];
}
}
}
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;
}
}
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 + df) {
X = at[dir^1];
if (a[to[X][dir]] >= mx) X = to[X][dir];
else X = bst[0][X][dir];
ass(a[X] >= mx);
}
}else{
walk(at);
if (a[at[dir]] >= mx+df) {
X = at[dir];
}else{
X = at[dir^1];
ass(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 |
1 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
768 KB |
Output is correct |
| 2 |
Correct |
27 ms |
19456 KB |
Output is correct |
| 3 |
Correct |
34 ms |
19456 KB |
Output is correct |
| 4 |
Correct |
28 ms |
19192 KB |
Output is correct |
| 5 |
Correct |
27 ms |
19328 KB |
Output is correct |
| 6 |
Correct |
30 ms |
19320 KB |
Output is correct |
| 7 |
Correct |
42 ms |
23032 KB |
Output is correct |
| 8 |
Correct |
26 ms |
22260 KB |
Output is correct |
| 9 |
Correct |
32 ms |
22392 KB |
Output is correct |
| 10 |
Correct |
28 ms |
20340 KB |
Output is correct |
| 11 |
Correct |
43 ms |
22392 KB |
Output is correct |
| 12 |
Correct |
44 ms |
20728 KB |
Output is correct |
| 13 |
Correct |
35 ms |
20216 KB |
Output is correct |
| 14 |
Correct |
36 ms |
22392 KB |
Output is correct |
| 15 |
Correct |
34 ms |
20728 KB |
Output is correct |
| 16 |
Correct |
35 ms |
20216 KB |
Output is correct |
| 17 |
Correct |
31 ms |
21632 KB |
Output is correct |
| 18 |
Correct |
31 ms |
21624 KB |
Output is correct |
| 19 |
Correct |
38 ms |
23928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2076 ms |
21260 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
25320 KB |
Output is correct |
| 2 |
Incorrect |
229 ms |
25320 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
