Submission #1016301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016301		hotboy2703	Ancient Books (IOI17_books)	C++17	100 / 100	490 ms	94296 KiB

books

#include "books.h"

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 1e6+100;
ll cnt[MAXN];
bool in[MAXN];
pll rg[MAXN];
ll dist[MAXN];
long long minimum_walk(std::vector<int> p, int s) {
    ll n = sz(p);
    for (ll i = 0;i < sz(p);i ++){
        if (p[i] > i){
            cnt[i]++,cnt[p[i]]--;
        }
    }
    for (ll i = 1;i < n;i ++)cnt[i] += cnt[i-1];
    int l = n + 1,r = -1;
    ll res=0;
    for (int i = 0;i < n;i ++){
        if (cnt[i]){
            res += cnt[i] * 2 - 2;
            l = min(l,i);
            r = max(r,i+1);
        }
    }
    l = min(l,s);
    r = max(r,s);
    res += (r-l)*2;
    if (s&&cnt[s]&&cnt[s-1]){
        for (ll i = 0;i < n; i ++){
            if (!in[i]){
                ll cur = i;
                vector <ll> all;
                while (!in[cur]){
                    all.push_back(cur);
                    in[cur] = 1;
                    cur = p[cur];
                }
                ll min1,max1;
                min1=n+1,max1=-1;
                for (auto x:all){
                    min1 = min(min1,x);
                    max1 = max(max1,x);
                }
                for (auto x:all)rg[x] = MP(min1,max1);
            }
        }
        memset(in,0,sizeof in);
        ll ptr = s;
        while (cnt[ptr])ptr++;
        vector <ll> q;
        q.push_back(s);
        set <ll> sus;
        for (ll i = 0;i < n;i ++){
            sus.insert(i);
        }
        sus.erase(s);
        while (!q.empty()){
            for (ll j = 0;j < sz(q);j ++){
                ll x = q[j];
                for (auto it = sus.lower_bound(rg[x].fi); it != sus.end() && (*it) <= rg[x].se;it = sus.erase(it)){
                    dist[*it] = dist[x];
                    q.push_back(*it);
                }
            }
            vector <ll> tmp;
            for (ll j = 0;j < sz(q);j ++){
                ll x = q[j];
                if (x + 1 < n && sus.find(x+1)!=sus.end()){
                    dist[x+1] = dist[x] + 1;
                    tmp.push_back(x+1);
                    sus.erase(x+1);
                }
                if (x-1>=0 && sus.find(x-1)!=sus.end()){
                    dist[x-1] = dist[x] + 1;
                    tmp.push_back(x-1);
                    sus.erase(x-1);
                }
            }
            swap(q,tmp);
        }
        res+=dist[ptr]*2;
    }
	return res;
}

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