#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
//#include "books.h"
using namespace std;
const int MX = 1e6 + 100;
pii v[MX];
int mn[MX], mx[MX], tmpn[MX], tmpx[MX];
unordered_map<int, int> dp[MX];
int dfs(int l, int r, int a, int b) {
if(l == a and r == b) return 0;
if(dp[l].find(r) != dp[l].end()) return dp[l][r];
if(l == a) return 2 + dfs(l, v[r + 1].S, a, b);
if(r == b) return 2 + dfs(v[l - 1].F, r, a, b);
int l1 = min(v[l - 1].F, l);
int r1 = max(v[l - 1].S, r);
int l2 = min(v[r + 1].F, l);
int r2 = max(v[r + 1].S, r);
if(r1 > r) return dp[l][r] = 2 + dfs(l1, r1, a, b);
else return dp[l][r] = 2 + dfs(l2, r2, a, b);
return dp[l][r] = 2 + min(dfs(l1, r1, a, b), dfs(l2, r2, a, b));
}
long long minimum_walk(vector<int> p, int s) {
int x = 0, y = p.size() - 1;
while(x < s and p[x] == x) x ++;
while(y > s and p[y] == y) y --;
for(int i = x; i <= y; i ++) mn[i] = mx[i] = i;
for(int i = x; i <= y; i ++) {
mn[i] = min(mn[i], p[i]);
mx[i] = max(mx[i], p[i]);
mn[p[i]] = min(mn[p[i]], i);
mx[p[i]] = max(mx[p[i]], i);
}
long long sum = 0;
for(int i = x; i <= y; i ++) sum += abs(p[i] - i);
auto update = [&] (int p, int a) {
mn[p] = min(mn[p], mn[a]);
mx[p] = max(mx[p], mx[a]);
};
int cnta = -2, cntb = -2;
{
memcpy(tmpn, mn, sizeof(mn));
memcpy(tmpx, mx, sizeof(mx));
queue<int> a, b;
for(int i = s - 1; i >= x; i --) a.push(i);
for(int i = s + 1; i <= y; i ++) b.push(i);
for(int i = s; i <= y; i ++) {
cnta += 2;
while(1) {
if(a.size() and a.front() >= mn[i]) update(i, a.front()), a.pop();
else if(b.size() and b.front() <= mx[i]) update(i, b.front()), b.pop();
else break;
}
v[i] = {mn[i], mx[i]};
i = mx[i];
}
memcpy(mn, tmpn, sizeof(mn));
memcpy(mx, tmpx, sizeof(mx));
}
{
memcpy(tmpn, mn, sizeof(mn));
memcpy(tmpx, mx, sizeof(mx));
queue<int> a, b;
for(int i = s - 1; i >= x; i --) a.push(i);
for(int i = s + 1; i <= y; i ++) b.push(i);
for(int i = s; i >= x; i --) {
cntb += 2;
while(1) {
if(a.size() and a.front() >= mn[i]) update(i, a.front()), a.pop();
else if(b.size() and b.front() <= mx[i]) update(i, b.front()), b.pop();
else break;
}
v[i] = {mn[i], mx[i]};
i = mn[i];
}
memcpy(mn, tmpn, sizeof(mn));
memcpy(mx, tmpx, sizeof(mx));
}
int mxx = v[s].S, mnn = v[s].F;
for(int i = s; i >= x; i --) mxx = max(mxx, v[i].S);
for(int i = s; i <= y; i ++) mnn = min(mnn, v[i].F);
return sum + min(cntb + dfs(x, mxx, x, y), cnta + dfs(mnn, y, x, y));
}
main () {
cout << minimum_walk({0, 2, 3, 1}, 0) << endl;
cout << minimum_walk({2, 3, 0, 1}, 0) << endl;
}
Compilation message
books.cpp:85:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
/tmp/cc16HG3M.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc3NZoLo.o:books.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
