#include "books.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
ll minimum_walk(vi p, int s) {
int n = p.size();
ll ans = 0;
vi visited; visited.assign(n,0);
vi left; left.assign(n,0);
vi right; right.assign(n,0);
vi rightInt, leftInt; rightInt.assign(n,0); leftInt.assign(n,0);
vi rightEmpty, leftEmpty; rightEmpty.assign(n,1); leftEmpty.assign(n,1);
RE(i,n)
ans += (ll)abs(i-p[i]);
RE(i,n) {
if(visited[i]) continue;
left[i] = i, right[i] = i;
if(i == p[i]) continue;
int u = p[i];
while(u != i) {
visited[u] = 1;
left [i] = min(left [i], u);
right[i] = max(right[i], u);
u = p[u];
}
u = p[i];
while(u != i) {
left [u] = left [i];
right[u] = right[i];
u = p[u];
}
}
REV(i,s,n) {
if(i != n-1)
rightInt[i] = rightInt[i+1];
if(i != n-1)
rightEmpty[i] = rightEmpty[i+1];
if(left[i] <= s)
rightInt[i] = 1;
if(left[i] != right[i])
rightEmpty[i] = 0;
}
REP(i,0,s+1) {
if(i != 0)
leftInt[i] = leftInt[i-1];
if(i != n-1)
leftEmpty[i] = leftEmpty[i-1];
if(right[i] >= s)
leftInt[i] = 1;
if(left[i] != right[i])
leftEmpty[i] = 0;
}
function<int(int)> getLeftSize = [&](int x) {
static vi mem(n,-1);
if(mem[x] != -1)
return mem[x];
int i = x;
int res = 0;
int leftSide = x;
int firstInt = INF;
while(i-- > 0) {
if(!leftInt[i])
return mem[x] = leftEmpty[i] ? int(INF) : 1;
if(i < leftSide)
res++;
if(right[i] >= s)
return mem[x] = res;
if(firstInt == INF && left[i] != right[i]) {
firstInt = res;
}
leftSide = min(leftSide, left[i]);
}
return mem[x] = firstInt;
};
function<int(int)> getRightSize = [&](int x) {
static vi mem(n,-1);
if(mem[x] != -1)
return mem[x];
int i = x;
int res = 0;
int rightSide = i;
int firstInt = INF;
while(i++ < n-1) {
if(!rightInt[i])
return mem[x] = rightEmpty[i] ? int(INF) : 1;
if(i > rightSide)
res++;
if(left[i] <= s)
return mem[x] = res;
if(firstInt == INF && left[i] != right[i]) {
firstInt = res;
}
rightSide = max(rightSide, right[i]);
}
return mem[x] = firstInt;
};
int ls=s, rs=s, nls=s, nrs=s;
queue<int> q; q.push(s);
while(true) {
while(!q.empty()) {
int i = q.front(); q.pop();
if(i == p[i]) continue;
int u = p[i];
while(u != i) {
while(ls > u) q.push(--ls);
while(rs < u) q.push(++rs);
u = p[u];
}
}
if(nls < ls || nrs > rs) {
while(ls > nls) {
q.push(--ls);
ans += 2ll;
if(left[ls] != right[ls])
break;
}
while(rs < nrs) {
q.push(++rs);
ans += 2ll;
if(left[rs] != right[rs])
break;
}
continue;
}
int leftSize = getLeftSize(ls), rightSize = getRightSize(rs);
if(leftSize == INF && rightSize == INF)
break;
if(leftSize < rightSize) {
nls = ls - leftSize;
} else {
nrs = rs + rightSize;
}
}
return ans;
}
#include "grader.cpp"
Compilation message
/usr/bin/ld: /tmp/ccztvTGj.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvBcSaj.o:books.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
