// vaziat meshki-ghermeze !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 1e5 + 10;
const int Inf = N + N;
const ll Log = 30;
int n, k, q;
int a[N], sz[N];
int L[N], wL[N], l[N], szl[N];
int R[N], wR[N], r[N], szr[N];
typedef pair<int, int> pii;
typedef pair<int, int> T;
typedef pair<int, T> P;
P nxt(T A){
pii lf = {wL[A.F], -a[L[A.F]]};
pii rt = {wR[A.S], -a[R[A.S]]};
if(lf == rt)
return {lf.F, {L[A.F], R[A.S]} };
if(lf < rt)
return {lf.F, {L[A.F], L[A.F]} };
return {rt.F, {R[A.S], R[A.S]}};
}
int Edge(int u, int v){
if(u > v) swap(u, v);
int res = Inf;
if(R[u] > v)
res = min(res, szl[v] - szl[u]);
if(L[v] < u)
res = min(res, szr[u] - szr[v]);
if(res < 0){
debug(res);
cerr << "!! " << u << ' ' << v << '\n';
cerr << "## " << szl[u] << ' ' << szl[v] << '\n';
assert(false);
}
return res;
}
const int FN = 11;
int dp[FN][FN];
int Floyd(vector<int> V, vector<int> S, vector<int> T){
int res = Inf;
int _n = V.size();
memset(dp, 31, sizeof dp);
for(int i = 0; i < _n; i++)
for(int j = 0; j < _n; j++)
dp[i][j] = dp[j][i] = Edge(V[i], V[j]);
for(int k = 0; k < _n; k++)
for(int i = 0; i < _n; i++)
for(int j = 0; j < _n; j++)
dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j]);
for(auto sr : S)
for(auto ds : T)
res = min(res, dp[sr][ds]);
return res;
}
int sp[N+N][Log], po = 0;
int WW[N+N][Log];
map<T, int> mp;
// map<int, T> rv;
T rv[N];
int Calc(T A){
if(mp.count(A))
return mp[A];
int i = po ++;
rv[i] = A;
mp[A] = i;
if(A.F == 0 || A.S == n + 1){
fill(sp[i], sp[i] + Log, i);
fill(WW[i], WW[i] + Log, Inf);
return i;
}
T B = nxt(A).S;
int ww = nxt(A).F;
int nx = Calc(B);
sp[i][0] = nx;
WW[i][0] = ww;
for(int l = 1; l < Log; l++){
sp[i][l] = sp[sp[i][l - 1]][l - 1];
WW[i][l] = WW[i][l - 1] + WW[sp[i][l - 1]][l - 1];
}
return i;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
a[0] = a[n + 1] = k + 1;
{ // stack
vector<int> V = {0};
for(int i = 1; i <= n; i++){
while(a[V.back()] < a[i]) V.pop_back();
l[i] = V.back();
V.pb(i);
sz[i] = V.size();
}
V = {0};
for(int i = 1; i <= n; i++){
while(a[V.back()] <= a[i]) V.pop_back();
L[i] = V.back();
V.pb(i);
}
sz[0] = 1; wL[0] = n; l[0] = L[0] = 0;
for(int i = 1; i <= n; i++)
wL[i] = L[i] != 0 ? sz[i] - sz[L[i]] : Inf;
memcpy(szl, sz, sizeof sz);
V = {n + 1};
for(int i = n; i >= 1; i--){
while(a[V.back()] < a[i]) V.pop_back();
r[i] = V.back();
V.pb(i);
sz[i] = V.size();
}
V = {n + 1};
for(int i = n; i >= 1; i--){
while(a[V.back()] <= a[i]) V.pop_back();
R[i] = V.back();
V.pb(i);
}
sz[n + 1] = 1; wR[n + 1] = n; r[n + 1] = R[n + 1] = n + 1;
for(int i = 1; i <= n; i++)
wR[i] = R[i] != n + 1 ? sz[i] - sz[R[i]] : Inf;
memcpy(szr, sz, sizeof sz);
}
// auto res = nxt({3, 3});
// cerr << res.F << ' ' << res.S.F << ' ' << res.S.S << '\n';
// debug(Edge(5, 1));
// debug(R[1]);
// exit(0);
int src, des;
for(int i = 0; i < q; i++){
cin >> src >> des;
if(src > des) swap(src, des);
// int idx = max_element(a + src, a + des + 1) - a;
// int mx = a[idx];
int lx = src, rx = des;
while(R[lx] <= des) lx = R[lx];
while(src <= L[rx]) rx = L[rx];
int mx = a[lx];
// for(int j = src; j <= des; j++) if(a[j] == mx) rx = j;
// for(int j = src; j <= des; j++) if(a[j] == mx){ lx = j; break; }
pii s1 = {src, src};
int id = Calc(s1);
int res = 0;
int cnt = 0;
for(int l = Log - 1; l >= 0; l--){
if(a[ rv[ sp[id][l] ].F ] >= mx) continue;
res += WW[id][l];
id = sp[id][l];
}
// debug(res);
// while(a[s1.F] < mx){
// auto del = nxt(s1);
// if(a[del.S.F] >= mx) break;
// cnt ++;
// res += del.F;
// s1 = del.S;
// }
// debug(res);
// assert(s1 == rv[id]);
s1 = rv[id];
// cerr << "!! " << s1.F << ' ' << s1.S << ' ' << rv[id].F << ' ' << rv[id].S << '\n';
pii s2 = {des, des};
id = Calc(s2);
while(a[s2.F] < mx){
auto del = nxt(s2);
if(a[del.S.F] >= mx) break;
cnt ++;
res += del.F;
s2 = del.S;
}
assert(cnt < k + k + 10);
// cerr << "$$ " << s2.F << ' ' << s2.S << ' ' << res << '\n';
// debug(Edge(5, 1));
// debug(Edge(1, 9));
vector<int> nodes = {lx, rx, s1.F, s1.S, s2.F, s2.S};
vector<int> S = {2, 3};
vector<int> T = {4, 5};
if(L[lx] != 0) nodes.pb(L[lx]);
if(R[rx] != n + 1) nodes.pb(R[rx]);
if(l[lx] != 0) nodes.pb(l[lx]);
if(r[rx] != n + 1) nodes.pb(r[rx]);
cout << res -1 + Floyd(nodes, S, T) << '\n';
}
return 0;
}
/*
9 3 3
3 1 1 1 2 2 2 3 3
2 4
4 9
6 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1136 KB |
Output is correct |
| 2 |
Correct |
16 ms |
4352 KB |
Output is correct |
| 3 |
Correct |
17 ms |
4340 KB |
Output is correct |
| 4 |
Correct |
17 ms |
4300 KB |
Output is correct |
| 5 |
Correct |
17 ms |
4300 KB |
Output is correct |
| 6 |
Correct |
17 ms |
4316 KB |
Output is correct |
| 7 |
Correct |
19 ms |
4300 KB |
Output is correct |
| 8 |
Correct |
13 ms |
4764 KB |
Output is correct |
| 9 |
Correct |
44 ms |
16904 KB |
Output is correct |
| 10 |
Correct |
33 ms |
11880 KB |
Output is correct |
| 11 |
Correct |
29 ms |
9200 KB |
Output is correct |
| 12 |
Correct |
30 ms |
9376 KB |
Output is correct |
| 13 |
Correct |
28 ms |
9968 KB |
Output is correct |
| 14 |
Correct |
30 ms |
9380 KB |
Output is correct |
| 15 |
Correct |
30 ms |
9180 KB |
Output is correct |
| 16 |
Correct |
31 ms |
9724 KB |
Output is correct |
| 17 |
Correct |
18 ms |
4360 KB |
Output is correct |
| 18 |
Correct |
20 ms |
4300 KB |
Output is correct |
| 19 |
Correct |
16 ms |
4300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
447 ms |
70736 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
616 ms |
32260 KB |
Output is correct |
| 2 |
Correct |
660 ms |
32272 KB |
Output is correct |
| 3 |
Correct |
545 ms |
32308 KB |
Output is correct |
| 4 |
Correct |
598 ms |
32324 KB |
Output is correct |
| 5 |
Correct |
481 ms |
31152 KB |
Output is correct |
| 6 |
Execution timed out |
2080 ms |
22652 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
