Submission #767219

#	Time	Username	Problem	Language	Result	Execution time	Memory
767219		danikoynov	Ancient Books (IOI17_books)	C++14	100 / 100	153 ms	65692 KiB

books

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

using namespace std;
typedef long long ll;


const int maxn = 1e6 + 10;
const ll inf = 1e18;
ll used[maxn];
int  lb[maxn], rb[maxn], n;
int bef[maxn], aft[maxn];
vector < int > st[maxn];

int l, r, cnt;
void extend(int left, int right)
{
    while(l > left || r < right)
    {
        if (l > left)
        {
            l --;
            if (used[l] != 0)
            {
            left = min(left, lb[used[l]]);
            right = max(right, rb[used[l]]);
            }
        }
        if (r < right)
        {
            r ++;
            if (used[r] != 0)
            {
            left = min(left, lb[used[r]]);
            right = max(right, rb[used[r]]);
            }
        }
    }
}

ll left_cost(int to)
{
    int gt = l, cost = 0;
    for (int i = l - 1; i >= to; i --)
    {
        if (used[i] == 0)
            continue;
        if (gt > i)
        cost = cost + (gt - i) * 2;
        gt = min(gt, lb[used[i]]);
    }
    return cost;
}

ll right_cost(int to)
{
    int gt = r, cost = 0;
    for (int i = r + 1; i <= to; i ++)
    {
        if (used[i] == 0)
            continue;
        if (gt < i)
            cost = cost + (i - gt) * 2;
        gt = max(gt, rb[used[i]]);
    }
    return cost;
}
long long minimum_walk(vector<int> p, int s)
{
    n = p.size();

    int cnt = 0;
    ll ans = 0;
    for (int i = 0; i < n; i ++)
    {
        ans = ans + abs(p[i] - i);
        if (p[i] == i)
            continue;
        if (used[i])
            continue;

        cnt ++;
        used[i] = cnt;
        int v = p[i];
        lb[cnt] = i;
        rb[cnt] = i;
        st[cnt].push_back(i);
        while(v != i)
        {
            st[cnt].push_back(v);
            used[v] = cnt;
            rb[cnt] = max(rb[cnt], v);
            v = p[v];
        }
    }
    l = s + 1;
    r = s;
    extend(s, s);
    while(true)
    {
        ///cout << l << " " << r << " " << ans << endl;
        int bf = l - 1, af = r + 1;
        while(bf >= 0)
        {
            if (used[bf] == 0)
            {
                bf --;
                continue;
            }
            if (lb[used[bf]] < l && rb[used[bf]] > r)
                break;
            bf --;
        }
        while(af < n)
        {
            if (used[af] == 0)
            {
                af ++;
                continue;
            }
            if (lb[used[af]] < l && rb[used[af]] > r)
                break;
            af ++;
        }

        if (bf != -1)
        {
            ll lc = left_cost(bf);
            ll rc = right_cost(af);
            ans = ans + min(lc, rc);
            extend(bf, af);
        }
        else
        {
                        ll lc = left_cost(0);
            ll rc = right_cost(n - 1);
            ///scout << lc << " " << rc << endl;
            ans = ans + lc + rc;
            break;
        }
    }

    ///cout << dp[lf][rf] << endl;
    ///cout << lf << " " << rf << endl;
    return ans;


}

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