제출 #46911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46911		SpaimaCarpatilor	고대 책들 (IOI17_books)	C++17	50 / 100	423 ms	174972 KiB

books

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

using namespace std;

int nr, N, S, p[1000009], prv[1000009], nxt[1000009], lg[1000009], mi[22][1000009], ma[22][1000009];
bool ap[1000009];
pair < int, int > segm[1000009];

pair < int, int > getMiMa (int l, int r)
{
    int p = lg[r - l + 1];
    return {min (mi[p][l], mi[p][r - (1 << p) + 1]), max (ma[p][l], ma[p][r - (1 << p) + 1])};
}

long long minimum_walk (vector < int > pp, int ss)
{
    N = pp.size (), S = ss + 1;
    for (int i=1; i<=N; i++)
        p[i] = pp[i - 1] + 1;
    for (int i=1; i<=N; i++)
        if (ap[i] == 0)
        {
            int j = p[i], maxRight = i;
            ap[i] = 1;
            while (j != i)
                ap[j] = 1, maxRight = max (maxRight, j), j = p[j];
            nxt[i] = maxRight, prv[i] = i, j = p[i];
            while (j != i)
                nxt[j] = maxRight, prv[j] = i, j = p[j];
        }
    long long ans = 0;
    for (int i=1; i<=N; i++)
    {
        int curr = i - p[i];
        if (curr < 0) curr = -curr;
        ans += curr;
    }
    for (int i=1; i<=N; i++)
        mi[0][i] = prv[i], ma[0][i] = nxt[i];
    for (int i=1; i<=N; i++)
    {
        lg[i] = lg[i - 1];
        if ((2 << lg[i]) <= i) lg[i] ++;
    }
    for (int i=1; i<=lg[N]; i++)
        for (int j=1; j + (1 << i) - 1 <= N; j ++)
            mi[i][j] = min (mi[i - 1][j], mi[i - 1][j + (1 << (i - 1))]),
            ma[i][j] = max (ma[i - 1][j], ma[i - 1][j + (1 << (i - 1))]);
    for (int i=1; i<=N; i++)
        if ((i == S || i != p[i]) && ap[i] == 1)
        {
            int l = i, r = i;
            while (1)
            {
                auto curr = getMiMa (l, r);
                if (l == curr.first && r == curr.second) break;
                l = curr.first;
                r = curr.second;
            }
            for (int j=l; j<=r; j++)
                ap[j] = 0;
            segm[++nr] = {l, r};
        }
    for (int i=1; i<nr; i++)
        ans += 2LL * (segm[i + 1].first - segm[i].second);
    return ans;
}

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