Submission #286380

#	Time	Username	Problem	Language	Result	Execution time	Memory
286380		Mercenary	Ancient Books (IOI17_books)	C++14	100 / 100	318 ms	22776 KiB

books

#ifndef LOCAL
#include "books.h"
#endif

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

long long minimum_walk(std::vector<int> p, int s) {
    int n = p.size();
    int L = 0, R = n - 1;
    while (L < s && p[L] == L)++L;
    while (R > s && p[R] == R)--R;
    ll res = 0;
    vector<int> mn(n , -1);
    vector<int> mx(n , -1);
    for(int i = 0 ; i < n ; ++i){
        res += abs(i - p[i]);
        if(mn[i] != -1)continue;
        int j = i;
        while(true){
            mn[j] = i;
            mx[i] = max(mx[i] , j);
            if(p[j] == i)break;
            j = p[j];
        }
        j = i;
        while(true){
            mx[j] = mx[i];
            if(p[j] == i)break;
            j = p[j];
        }
    }
    int valL = 0, valR = 0;
    for (int i = L, tmp = 0; i < s; ++i)
    {
        tmp = max(tmp , mx[i]);
        if(tmp == i)valL += 2;
    }
    for (int i = R, tmp = n; i > s; --i)
    {
        tmp = min(tmp, mn[i]);
        if(tmp == i)valR += 2;
    }
    res += min(valL , valR);
    auto extend = [&](int & l , int & r , int ll , int rr){
        while(ll < l || r < rr){
            if(ll < l){
                --l;
                ll = min(ll , mn[l]);
                rr = max(rr , mx[l]);
            }
            if(r < rr){
                ++r;
                ll = min(ll , mn[r]);
                rr = max(rr , mx[r]);
            }
        }
    };
    int l = s , r = s;
    extend(l,r , mn[s] , mx[s]);
    while(L < l || r < R){
        res += 2;
        extend(l,r,max(L , l - 1),min(R,r+1));
    }
    return res;

}

#ifdef LOCAL
#include "books.h"

#include <cstdio>
#include <vector>
#include <cassert>

using namespace std;

int main() {
    freopen(taskname".INP","r",stdin);
	int n, s;
	assert(2 == scanf("%d %d", &n, &s));

	vector<int> p((unsigned) n);
	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &p[(unsigned) i]));

	long long res = minimum_walk(p, s);
	printf("%lld\n", res);

	return 0;
}

#endif // LOCAL

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