| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 152381 | qkxwsm | 고대 책들 (IOI17_books) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 1000013
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, S;
pii need = {-1, -1}, cur;
int dsu[MAXN];
pii range[MAXN];
vi arr;
ll ans;
int get(int u)
{
return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
bool merge(int u, int v)
{
u = get(u); v = get(v);
if (u == v) return false;
dsu[v] = u;
ckmin(range[u].fi, range[v].fi);
ckmax(range[u].se, range[v].se);
return true;
}
ll minimum_walk(vi perm, int s)
{
//mark all the blocks
N = SZ(perm); S = s; arr = perm;
FOR(i, 0, N)
{
dsu[i] = i;
range[i] = {i, i};
}
FOR(i, 0, N)
{
merge(i, arr[i]);
}
//so we have access to (l..r).
//what do we do? we constantly try to "expand" acess until we covered the entire needy range
FOR(i, 0, N)
{
if (arr[i] != i)
{
need.fi = i;
break;
}
}
FORD(i, N, 0)
{
if (arr[i] != i)
{
need.se = i;
break;
}
}
if (need.fi == -1) return 0ll;
ckmin(need.fi, S);
ckmax(need.se, S);
//implement the extend function? so for (l..r) you wanna be able to say basically the entire range that you get for free.
int lt = range[get(S)].fi, rt = range[get(S)].se;
cur = {S, S};
while(cur.fi > lt || cur.se < rt)
{
for (int i = cur.fi - 1; i >= lt; i--)
{
ckmin(lt, range[get(i)].fi);
ckmax(rt, range[get(i)].se);
}
cur.fi = lt;
for (int i = cur.se + 1; i <= rt; i++)
{
ckmin(lt, range[get(i)].fi);
ckmax(rt, range[get(i)].se);
}
cur.se = rt;
}
// cerr << cur.fi << ' ' << cur.se << ' ' << need.fi << ' ' << need.se << endl;
while(cur != need)
{
//you need to expand the rnage at minimum cost.
//find the first range you get
ll lc = 0, rc = 0;
int bound = cur.fi;
for (lt = cur.fi - 1; lt >= need.fi; lt--)
{
//see if you get a new guy.
if (bound == lt + 1) lc += 2;
pii p = range[get(lt)];
if (p.se > cur.se) break;
ckmin(bound, p.fi);
}
bound = cur.se;
for (rt = cur.se + 1; rt <= need.se; rt++)
{
if (bound == rt - 1) rc += 2;
pii p = range[get(rt)];
if (p.fi < cur.fi) break;
ckmax(bound, p.se);
}
// cerr << "lc " << lc << " rc " << rc << endl;
if (lt == need.fi - 1)
{
assert(rt == need.se + 1);
ans += lc;
ans += rc;
cur = need;
break;
}
ans += min(lc, rc);
//ok now expand the range.
while(cur.fi > lt || cur.se < rt)
{
for (int i = cur.fi - 1; i >= lt; i--)
{
ckmin(lt, range[get(i)].fi);
ckmax(rt, range[get(i)].se);
}
cur.fi = lt;
for (int i = cur.se + 1; i <= rt; i++)
{
ckmin(lt, range[get(i)].fi);
ckmax(rt, range[get(i)].se);
}
cur.se = rt;
}
}
FOR(i, 0, N)
{
ans += abs(arr[i] - i);
}
return ans;
}