Submission #1133602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133602		jerzyk	Ancient Books (IOI17_books)	C++20	100 / 100	128 ms	28884 KiB

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1000'007;
bool vis[N];
int tab[N], rp[N], lp[N];
vector<pair<int, int>> inter;
int dis[N];

int DoDis(int n, int s)
{
    int l, r, nl, nr, nd;
    l = s; r = s;
    for(int i = 0; i < n; ++i) dis[i] = II;
    dis[s] = 0;
    nd = 0;
    nl = lp[s]; nr = rp[s];
    while(l != nl || r != nr)
    {
        l = max(l - 1, nl); r = min(r + 1, nr);
        dis[l] = min(dis[l], nd); dis[r] = min(dis[r], nd);
        nl = min(nl, min(lp[r], lp[l])); nr = max(nr, max(rp[r], rp[l]));
    }
    while(l != 0 || r != n - 1)
    {
        //cerr << "R: " << l << " " << r << "\n";
        nd = max(dis[l], dis[r]) + 1;
        nl = max(0, l - 1); nr = min(n - 1, r + 1);
        while(l != nl || r != nr)
        {
            l = max(l - 1, nl); r = min(r + 1, nr);
            dis[l] = min(dis[l], nd); dis[r] = min(dis[r], nd);
            nl = min(nl, min(lp[r], lp[l])); nr = max(nr, max(rp[r], rp[l]));
        }
    }
    int ans = 0;
    for(int i = 0; i < (int)inter.size(); ++i)
        if(inter[i].nd >= s)
        {
            ans = dis[inter[i].st];
            break;
        }
    //cerr << "D: " << ans << "\n";
    return ans;
}

int Dl(int s)
{
    for(int i = s - 1; i >= 0; --i)
        if(tab[i] != i)
            return s - i;
    return 0;
}

int Dr(int s, int n)
{
    for(int i = s + 1; i < n; ++i)
        if(tab[i] != i)
            return i - s;
    return 0;
}

ll minimum_walk(vector<int> _p, int _s)
{
    int n = (int)_p.size();
    ll ans = 0LL;
    for(int i = 0; i < n; ++i)
    {
        rp[i] = i; lp[i] = i;
        tab[i] = _p[i];
    }
    bool czy = 0;
    for(int i = 0; i < n; ++i)
    {
        ans += (int)abs(tab[i] - i);
        if(vis[i]) continue;
        int l = i, r = i, v = i;
        vector<int> cur;
        while(!vis[v])
        {
            cur.pb(v);
            vis[v] = 1;
            l = min(l, v); r = max(r, v);
            v = tab[v];
        }
        //cerr << "FR: " << l << " " << r << "\n";
        for(int j = 0; j < (int)cur.size(); ++j)
            {rp[cur[j]] = r; lp[cur[j]] = l;}
        if(l != r)
            inter.pb(make_pair(l, r));
        if(l != r && l <= _s && r >= _s)
            czy = 1;
    }
    sort(inter.begin(), inter.end());
    if(czy)
        ans += DoDis(n, _s) * 2;
    else
    {
        int dl = Dl(_s), dr = Dr(_s, n);
        if(dl == 0 || dr == 0) 
            ans += (ll)(dl + dr) * 2LL;
    }
    int cur = 0;
    for(int i = 0; i < (int)inter.size(); ++i)
    {
        if(i != 0 && cur < inter[i].st) ans += 2LL * (ll)(inter[i].st - cur);
        cur = max(cur, inter[i].nd);
    }
    return ans;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30