Submission #425269

#	Time	Username	Problem	Language	Result	Execution time	Memory
425269		arayi	Ancient Books (IOI17_books)	C++17	100 / 100	263 ms	44372 KiB

books

#include "books.h"
#include <queue>
#include <algorithm>
#include <vector>
#define lli long long
#define ad push_back
#define fr first
#define sc second
#define MP make_pair
using namespace std;

const int N = 1e6 + 30;
const int mod = 1e9;

int i1 = 1, ii, n;
int col[N], a[N], cl[N];
int mn[N], mx[N], m[N], x[N], d[N];
lli ans;
int dfs(int v)
{
    col[v] = i1;
    cl[v] = ii;
    mn[ii] = min(mn[ii], v), m[i1] = min(m[i1], v);
    mx[ii] = max(mx[ii], v), x[i1] = max(x[i1], v);
    if (!col[a[v]]) return max(v, dfs(a[v]));
    return v;
}
long long minimum_walk(vector<int> p, int s)
{
    n = p.size();
    for (int i = 0; i < n; i++) a[i] = p[i], ans += abs(a[i] - i), mn[i] = m[i] = n, d[i] = mod;
    int nx = -1;
    for (int i = 0; i < n; i++)
    {
        if (a[i] == i) continue;
        if (!col[i])
        {
            if (nx >= 0 && i > nx) ans += 2 * (i - nx), i1++;
            ii++;
            nx = max(nx, dfs(i));
        }
    }
    int dz = -1, aj = -1;
    for (int i = s; i < n; i++)
    {
        if (col[i])
        {
            aj = i;
            break;
        }
    }
    for (int i = s; i >= 0; i--)
    {
        if (col[i])
        {
            dz = i;
            break;
        }
    }
    if (dz == -1 && aj == -1) return ans;
    else if (dz == -1) ans += 2 * abs(aj - s);
    else if (aj == -1) ans += 2 * abs(s - dz);
    else if (col[aj] == col[dz])
    {
        priority_queue < pair<pair<int, int>, pair<int, int> > > q;
        q.push(MP(MP(s - aj, cl[aj]), MP(s, s)));
        q.push(MP(MP(dz - s, cl[dz]), MP(s, s)));
        while (!q.empty())
        {
            int d = q.top().fr.fr, v = q.top().fr.sc, l = q.top().sc.fr, r = q.top().sc.sc;
            q.pop();
            if (::d[v] != mod) continue;
            ::d[v] = -d;
            int l1 = min(l, mn[v]), r1 = max(r, mx[v]);
            while (l1 < l || r1 > r)
            {
                if (l1 < l)
                {
                    l--;
                    if (cl[l] && ::d[cl[l]] == mod) ::d[cl[l]] = -d, l1 = min(l1, mn[cl[l]]), r1 = max(r1, mx[cl[l]]);
                }
                if (r1 > r)
                {
                    r++;
                    if (cl[r] && ::d[cl[r]] == mod) ::d[cl[r]] = -d, l1 = min(l1, mn[cl[r]]), r1 = max(r1, mx[cl[r]]);
                }
            }
            if (l1 == m[col[aj]]) break;
            for (int i = r1 + 1; i < n; i++)
            {
                if (cl[i])
                {
                    q.push(MP(MP(d - (i - r1), cl[i]), MP(l1, r1)));
                    break;
                }
            }
            for (int i = l1 - 1; i >= 0; i--)
            {
                if (cl[i])
                {
                    q.push(MP(MP(d - (l1 - i), cl[i]), MP(l1, r1)));
                    break;
                }
            }
        }
        ans += 2 * d[cl[m[col[aj]]]];
    }
    return ans;
}

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