#include "bits/stdc++.h"
using namespace std;
#define right sadfsdf
#define left sfdfdff
int n, k, q;
int a[100010];
int left[100010];
int right[100010];
int lid[100010];
int rid[100010];
int l[100010];
int r[100010];
typedef pair <int, int> pii;
vector <int> g[100010];
int dp[2][2][20][100010];
int par[20][100010];
const int logn = 19;
int dep[200010];
int pos[200010];
const int inf = 1e9;
void dfs(int x) {
for(auto i : g[x]) {
dep[i] = 1 + dep[x];
dfs(i);
}
}
int lca(int p, int q) {
if(dep[p] > dep[q]) swap(p, q);
for(int i = logn; i >= 0; i--) {
if(dep[q] - (1 << i) >= dep[p]) {
q = par[i][q];
}
}
if(p == q) return p;
for(int i = logn; i >= 0; i--) {
if(par[i][p] != par[i][q]) {
p = par[i][p];
q = par[i][q];
}
}
return par[0][p];
}
int lift(int p, int depth) {
for(int i = logn; i >= 0; i--) {
if(dep[p] - (1 << i) >= depth) {
p = par[i][p];
}
}
return p;
}
int dist(int p, int x, int q, int y) {
int idp = pos[p];
int idq = pos[q];
if(idp > idq) {
swap(idp, idq);
swap(x, y);
swap(p, q);
}
int opt = inf;
opt = min(opt, idq + y - idp - x);
if(par[0][p]) opt = min(opt, dp[x][0][0][p] + dp[y][1][0][q] + 1);
if(par[0][p]) opt = min(opt, dp[x][1][0][p] + dp[y][0][0][q] + 1);
return opt;
}
int distance(int p, int x, int q, int y) {
if(p == 0 || q == 0) return inf;
if(dep[p] > dep[q]) {
swap(p, q);
swap(x, y);
}
int anc = lca(p, q);
int pd[2];
int qd[2];
memset(pd, 0, sizeof pd);
memset(qd, 0, sizeof qd);
pd[x ^ 1] = 1;
qd[y ^ 1] = 1;
for(int i = logn; i >= 0; i--) {
if(dep[p] - (1 << i) > dep[anc]) {
int aa = min(pd[1] + dp[1][0][i][p], pd[0] + dp[0][0][i][p]);
int bb = min(pd[1] + dp[1][1][i][p], pd[0] + dp[0][1][i][p]);
p = par[i][p];
pd[0] = aa;
pd[1] = bb;
}
}
// cout << p << " " << "pd " << pd[0] << " " << pd[1] << endl;
for(int i = logn; i >= 0; i--) {
if(dep[q] - (1 << i) > dep[anc]) {
int aa = min(qd[1] + dp[1][0][i][q], qd[0] + dp[0][0][i][q]);
int bb = min(qd[1] + dp[1][1][i][q], qd[0] + dp[0][1][i][q]);
q = par[i][q];
qd[0] = aa;
qd[1] = bb;
// cout << q << " " << "qd " << qd[0] << " " << qd[1] << endl;
}
}
// cout << q << " " << "qd " << qd[0] << " " << qd[1] << endl;
int ans = inf;
if(p != anc) {
for(int i = 0; i <= 1; i++) {
for(int j = 0; j <= 1; j++) {
ans = min(ans, pd[i] + qd[j] + dist(p, i, q, j));
// cout << i << ' ' << j << ' ' << dist(p, i, q, j) << endl;
}
}
} else {
for(int i = 0; i <= 1; i++) {
for(int j = 0; j <= 1; j++) {
ans = min(ans, pd[i] + qd[j] + dp[j][i][0][q]);
}
}
}
// cout << ans-1 << endl;
return ans-1;
}
map <pii, int> range_id;
int query(int x, int y) {
if(x == y) return 0;
int ans = inf;
int lx = range_id[pii(left[x], x)];
int rx = range_id[pii(x, right[x])];
int ly = range_id[pii(left[y], y)];
int ry = range_id[pii(y, right[y])];
// cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << endl;
ans = min(ans, distance(lx, 1, ly, 1));
ans = min(ans, distance(lx, 1, ry, 0));
ans = min(ans, distance(rx, 0, ly, 1));
ans = min(ans, distance(rx, 0, ry, 0));
return ans;
}
int main(int argc, char const *argv[])
{
scanf("%d %d %d", &n, &k, &q);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int idx = 0;
stack <int> s;
set <pii> range;
for(int i = 1; i <= n; i++) {
while(!s.empty() && a[s.top()] < a[i]) {
s.pop();
}
if(i > 1) {
left[i] = s.top();
range.emplace(left[i], i);
}
s.push(i);
}
while(!s.empty()) s.pop();
for(int i = n; i >= 1; i--) {
while(!s.empty() && a[s.top()] < a[i]) {
s.pop();
}
if(i < n) {
right[i] = s.top();
range.emplace(i, right[i]);
}
s.push(i);
}
for(auto i : range) {
l[++idx] = i.first;
r[idx] = i.second;
range_id[i] = idx;
// cout << l[idx] << ' ' << r[idx] << ' ' << idx << endl;
}
vector <pii> v;
for(int i = 1; i <= idx; i++) {
v.emplace_back(pii(r[i] - l[i], i));
}
sort(v.begin(), v.end());
set <pii> ss;
for(auto i : v) {
int p = l[i.second];
int q = r[i.second];
while(true) {
auto it = ss.lower_bound(pii(p, -1));
if(it == ss.end()) break;
if(r[it -> second] <= q) {
par[0][it -> second] = i.second;
g[i.second].emplace_back(it -> second);
ss.erase(it);
} else {
break;
}
}
ss.insert(pii(p, i.second));
}
for(auto i : ss) {
g[0].emplace_back(i.second);
par[0][i.second] = 0;
}
for(int i = 1; i <= logn; i++) {
for(int j = 1; j <= idx; j++) {
par[i][j] = par[i - 1][par[i - 1][j]];
}
}
for(int i = 0; i <= idx; i++) {
int id = 0;
for(auto j : g[i]) {
// cout << i << ' ' << j << endl;
dp[0][0][0][j] = id;
dp[0][1][0][j] = g[i].size() - id;
dp[0][0][0][j] = min(dp[0][0][0][j], 1 + dp[0][1][0][j]);
dp[0][1][0][j] = min(dp[0][1][0][j], 1 + dp[0][0][0][j]);
dp[1][0][0][j] = id + 1;
dp[1][1][0][j] = g[i].size() - id - 1;
dp[1][0][0][j] = min(dp[1][0][0][j], 1 + dp[1][1][0][j]);
dp[1][1][0][j] = min(dp[1][1][0][j], 1 + dp[1][0][0][j]);
pos[j] = ++id;
}
}
for(int i = 1; i <= logn; i++) {
for(int j = 0; j <= 1; j++) {
for(int k = 0; k <= 1; k++) {
for(int l = 0; l <= idx; l++) {
int opt = inf;
for(int x = 0; x <= 1; x++) {
opt = min(opt, dp[j][x][i - 1][l] + dp[x][k][i - 1][par[i - 1][l]]);
}
dp[j][k][i][l] = opt;
}
}
}
}
dfs(0);
for(int i = 1; i <= q; i++) {
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", query(x, y));
}
return 0;
}
Compilation message
railway_trip.cpp: In function 'int main(int, const char**)':
railway_trip.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &k, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
railway_trip.cpp:243:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3324 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3404 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3444 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3444 KB |
Output is correct |
| 5 |
Correct |
5 ms |
3444 KB |
Output is correct |
| 6 |
Correct |
7 ms |
3504 KB |
Output is correct |
| 7 |
Correct |
6 ms |
3616 KB |
Output is correct |
| 8 |
Correct |
6 ms |
3640 KB |
Output is correct |
| 9 |
Correct |
5 ms |
3640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
4760 KB |
Output is correct |
| 2 |
Runtime error |
247 ms |
59448 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
267 ms |
61296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
311 ms |
66912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
