Submission #1155805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155805		alexdd	Ancient Books (IOI17_books)	C++20	50 / 100	76 ms	19952 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int p[1000005];
int maxpref[1000005],minsuff[1000005];
long long minimum_walk(std::vector<int> cit_p, int s)
{
    s++;
    n = cit_p.size();
    for(int i=1;i<=n;i++)
        p[i] = cit_p[i-1]+1;
    
    int ult=0;
    long long rez=0;
    for(int i=1;i<=n;i++)
    {
        maxpref[i] = max(maxpref[i-1], p[i]);
        if(p[i]!=i) ult=i;
        rez += abs(p[i]-i);
    }
    minsuff[n+1] = n+1;
    for(int i=n;i>0;i--)
        minsuff[i] = min(minsuff[i+1], p[i]);
    for(int i=2;i<=ult;i++)
    {
        if(maxpref[i-1]<i && minsuff[i]>=i)
            rez+=2;
    }
    return rez;
}

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