제출 #1218495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218495		andrej246	Ancient Books (IOI17_books)	C++20	100 / 100	847 ms	181116 KiB

books

#include "books.h"

#include <bits/stdc++.h>
using namespace std;

#define NL "\n"
#define EL cout << NL
#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i >= 0; i--)
#define PRINTV(v) for (auto a: v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a: v) {PRINTV(v);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;

vl dsu;
vl sz;

ll find(ll u) {
    if (dsu[u] == u) return u;
    return dsu[u] = find(dsu[u]);
}

void unite(ll a, ll b) {
    ll x = find(a);
    ll y = find(b);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x,y);
    sz[x] += sz[y];
    dsu[y] = x;
}

long long minimum_walk(std::vector<int> p, int s) {
    int farthest = 0;
    ll n = p.size();
    ll ans = 0;
    deque<ll> empty(n-1);
    dsu.resize(n);
    sz.assign(n,1);
    FOR(i,n) dsu[i] = i;
    FOR(i,n) unite(i,p[i]);
    FOR(i,n) {
        if (i > farthest) empty[i-1] = true;
        if (p[i] < i) continue;
        ans += 2*(p[i]-i);
        farthest = max(farthest,p[i]);
    }

    ll i = 0;
    while (i < s) {
        if (!empty.front()) break;
        empty.pop_front();
        i++;
    }

    i = n-2;
    while (i >= s) {
        if (!empty.back()) break;
        empty.pop_back();
        i--;
    }

    for (auto x: empty) ans += 2*x;

    set<pl> ranges;
    FOR(i,n) {
        ll a = i;
        ll b = p[i];
        if (a > b) swap(a,b);
        ranges.insert({a,b});
    }

    set<pl> open;
    vpl merged;
    for (auto [a,b]: ranges) {
        while (!open.empty() && (*open.begin()).f < a) {
            auto [y,x] = *open.begin();
            merged.push_back({x,y});
            open.erase(open.begin());
        }
        ll earliest = a;
        while (!open.empty() && (*open.begin()).f < b) {
            auto [y,x] = *open.begin();
            earliest = min(earliest,x);
            open.erase(open.begin());
            unite(x,a);
        }
        open.insert({b,earliest});
    }
    while (!open.empty() && (*open.begin()).f < n) {
        auto [y,x] = *open.begin();
        merged.push_back({x,y});
        open.erase(open.begin());
    }

    vl side1(n,1e18);
    vl side2(n,-1e18);

    FOR(i,n) {
        ll j = find(i);
        if (i <= s) side1[j] = min(side1[j],i);
        if (i >= s) side2[j] = max(side2[j],i);
    }

    ll id = -1;
    FOR(i,n) {
        ll j = find(i);
        if (side1[j] != 1e18 && side2[j] != -1e18) {
            id = j;
            break;
        }
    }

    vvl g(n);
    FOR(i,n-1) {
        ll a = find(i);
        ll b = find(i+1);
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vl dist(n,1e18);
    dist[find(s)] = 0;
    deque<ll> q;
    q.push_back(find(s));
    while (!q.empty()) {
        ll u = q.front();
        q.pop_front();
        for (auto v: g[u]) {
            if (dist[v] > dist[u]+1) {
                dist[v] = dist[u]+1;
                q.push_back(v);
            }
        }
    }

    ans += dist[id]*2;

    return ans;
}

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