Submission #294221

#	Time	Username	Problem	Language	Result	Execution time	Memory
294221		Kastanda	Ancient Books (IOI17_books)	C++11	0 / 100	1 ms	512 KiB

books

// M
#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
const int N = 1000006, LG = 20;
int n, st, A[N], mnq[LG][N], mxq[LG][N], Log[N];
map < pair < int , int > , pair < int , int > > MP;
inline int GetMin(int l, int r)
{
        int lg = Log[r - l];
        return min(mnq[lg][l], mnq[lg][r - (1 << lg)]);
}
inline int GetMax(int l, int r)
{
        int lg = Log[r - l];
        return max(mxq[lg][l], mxq[lg][r - (1 << lg)]);
}
inline pair < int , int > Extend(pair < int , int > nw)
{
        while (true)
        {
                pair < int , int > tb;
                tb.first = min(nw.first, GetMin(nw.first, nw.second + 1));
                tb.second = max(nw.second, GetMax(nw.first, nw.second + 1));
                if (tb == nw)
                        break;
                nw = tb;
        }
        return nw;
}

long long minimum_walk(vector < int > _A, int _st)
{
        n = (int)_A.size();
        st = _st + 1;
        for (int i = 1; i <= n; i ++)
                A[i] = _A[i - 1] + 1;

        for (int i = 2; i <= n; i ++)
                Log[i] = Log[i >> 1] + 1;
        for (int i = 1; i <= n; i ++)
                mnq[0][i] = mxq[0][i] = A[i];
        for (int j = 1; j < LG; j ++)
                for (int i = 1; i + (1 << j) <= n + 1; i ++)
                {
                        mnq[j][i] = min(mnq[j - 1][i], mnq[j - 1][i + (1 << (j - 1))]);
                        mxq[j][i] = max(mxq[j - 1][i], mxq[j - 1][i + (1 << (j - 1))]);
                }

        ll SM = 0;
        for (int i = 1; i <= n; i ++)
                SM += abs(A[i] - i);

        int Mn = 1, Mx = n;
        while (Mn < st && A[Mn] == Mn)
                Mn ++;
        while (Mx > st && A[Mx] == Mx)
                Mx --;

        pair < int , int > nw = {st, st};
        nw = Extend(nw);

        while (nw != make_pair(Mn, Mx))
        {
                int cle = 0, cri = 0;
                pair < int , int > gle = nw, gri = nw;
                while (gle.first > 1 && gle.second == nw.second)
                        cle ++, gle = Extend({gle.first - 1, gle.second});
                while (gri.second < n && gri.first == nw.first)
                        cri ++, gri = Extend({gri.first, gri.second + 1});
                if (gle == gri)
                        SM += min(cle, cri) * 2, nw = gle;
                else
                        SM += (cle + cri) * 2, nw = make_pair(Mn, Mx);
        }
        return SM;
}

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