Submission #1279696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279696		pvpro	Ancient Books (IOI17_books)	C++20	22 / 100	2107 ms	285080 KiB

books

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <complex>
#include <numeric>
#include <assert.h>
#include <functional>
#include <climits>
#include <cstring>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ushort = unsigned short;

#ifndef LOCAL
#define endl "\n"
#endif
#define f first
#define s second
#define vec vector
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
template<typename T1, typename T2>
istream& operator>> (istream &in, pair<T1, T2> &p) { in >> p.f >> p.s; return in; }
template<typename T1, typename T2>
ostream& operator<< (ostream &out, pair<T1, T2> p) { out << "(" << p.f << " " << p.s << ")"; return out; }
#define printv(v) cerr << #v << " "; for (auto &x : v) { cerr << x << " "; } cerr << endl;
#define printvv(v) cerr << #v << " "; for (auto &x : v) { for (auto &y : x) { cerr << y << " "; } cerr << endl; }
#define debug(x) cerr << #x << " " << x << endl;

template<typename T>
istream& operator>> (istream &in, vector<T> &v) {
    for (auto &x : v) {
        in >> x;
    }
    return in;
}
template<typename T>
ostream& operator<< (ostream &out, vector<T> v) {
    for (auto &x : v) {
        out << x << " ";
    }
    return out;
}
template<typename T>
void operator-=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x -= delta;
    }
}
template<typename T>
void operator+=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x += delta;
    }
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

struct DSU {
    vector<int> pr, high, l, r;
    DSU(vector<pii> segments) {
        int n = segments.size();
        pr.resize(n);
        high.assign(n, 1);
        iota(all(pr), 0);
        l.resize(n);
        r.resize(n);
        for (int i = 0; i < n; ++i) {
            l[i] = segments[i].f;
            r[i] = segments[i].s;
        }
    }
    int get(int v) {
        if (pr[v] != v) {
            pr[v] = get(pr[v]);
        }
        return pr[v];
    }
    bool unite(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) {
            return false;
        }
        if (high[a] < high[b]) {
            swap(a, b);
        }
//        cout << a << ' ' << b << endl;
        pr[b] = a;
        high[a] += high[b];
        l[a] = min(l[a], l[b]);
        r[a] = max(r[a], r[b]);
        return true;
    }
};

const int MAX_N = (1<<21);

struct ST {
    pii T[MAX_N * 2];
    vector<pii> segments;
    ST() {}
    void build() {
        segments.pb(mp(-1e9, -1e9));
        vector<pii> a(MAX_N, mp(segments.size() - 1, -1));
        for (int i = 0; i < segments.size() - 1; ++i) {
            if (segments[i].f == segments[i].s || segments[i].f == -segments[i].s) {
                continue;
            }
            if (a[segments[i].f * 2].f == segments.size() - 1) {
                a[segments[i].f * 2] = mp(i, segments[i].f * 2);
            } else {
                a[segments[i].f * 2 + 1] = mp(i, segments[i].f * 2 + 1);
            }
        }
        build(1, 0, MAX_N, a);
    }
    void build(int i, int l, int r, vector<pii> &a) {
        if (l + 1 == r) {
            T[i] = a[l];
        } else {
            int m = (l + r) / 2;
            build(i * 2, l, m, a);
            build(i * 2 + 1, m, r, a);
            T[i] = max(T[i * 2], T[i * 2 + 1], [&](const pii &a, const pii &b) {
                return segments[a.f].s < segments[b.f].s;
            });
        }
    }
    pii get(int i, int l, int r, int ql, int qr) {
        if (l >= qr || r <= ql) {
            return mp(segments.size() - 1, 0);
        }
        if (ql <= l && r <= qr) {
            return T[i];
        } else {
            int m = (l + r) / 2;
            return max(get(i * 2, l, m, ql, qr), get(i * 2 + 1, m, r, ql, qr), [&](const pii &a, const pii &b) {
                return segments[a.f].s < segments[b.f].s;
            });
        }
    }
    void update(int i, int l, int r, int ql) {
        if (l + 1 == r) {
            T[i] = mp(segments.size() - 1, -1);
            return;
        }
        int m = (l + r) / 2;
        if (m > ql) {
            update(i * 2, l, m, ql);
        } else {
            update(i * 2 + 1, m, r, ql);
        }
        T[i] = max(T[i * 2], T[i * 2 + 1], [&](const pii &a, const pii &b) {
            return segments[a.f].s < segments[b.f].s;
        });
    }
};

ST L, R;

ll minimum_walk(vector<int> p, int s) {
    int n = p.size();
    ll ans = 0;
    vector<pii> segments;
    segments.reserve(n + 1);
    for (int i = 0; i < n; ++i) {
        ans += abs(i - p[i]);
        if (i != p[i]) {
            segments.pb(mp(min(i, p[i]), max(i, p[i])));
        }
    }
    segments.pb(mp(s, s));
    sort(all(segments));
    L.segments = segments;
    L.build();
    for (auto &x : segments) {
        swap(x.f, x.s);
        x.s = -x.s;
    }
    R.segments = segments;
    R.build();
    for (auto &x : segments) {
        x.s = -x.s;
        swap(x.f, x.s);
    }
    vector<int> used(segments.size());
    DSU dsu(segments);
    auto dfs = [&](int v, auto &&self) -> void {
        if (used[v]) {
            return;
        }
        used[v] = true;
        while (true) {
            pii p = L.get(1, 0, MAX_N, segments[v].f * 2, segments[v].s * 2 + 1);
            if (p.f == segments.size()) {
                break;
            }
            if (segments[p.f].s >= segments[v].s) {
                dsu.unite(p.f, v);
                L.update(1, 0, MAX_N, p.s);
                self(p.f, self);
            } else {
                break;
            }
        }
        while (true) {
            pii p = R.get(1, 0, MAX_N, segments[v].f * 2, segments[v].s * 2 + 1);
            if (p.f == segments.size()) {
                break;
            }
            if (segments[p.f].f <= segments[v].f) {
                dsu.unite(p.f, v);
                R.update(1, 0, MAX_N, p.s);
                self(p.f, self);
            } else {
                break;
            }
        }
    };
    for (int i = 0; i < segments.size(); ++i) {
        if (segments[i].f == s && segments[i].s == s) {
            continue;
        }
        if (!used[i]) {
            dfs(i, dfs);
        }
    }
    int leftest = s, rightest = s;
    vector<int> bal(n);
    for (int i = 0; i < segments.size(); ++i) {
        leftest = min(leftest, segments[i].f);
        rightest = max(rightest, segments[i].s);
        ++bal[segments[i].f];
        --bal[segments[i].s];
    }
    int now = 0;
    for (int i = 0; i < n; ++i) {
        now += bal[i];
        if (now == 0 && i >= leftest && i < rightest) {
            ans += 2;
        }
    }
    if (s > 0) {
        vector<pii> pts;
        pts.reserve(segments.size() * 2);
        for (int i = 0; i < segments.size(); ++i) {
            pts.pb(mp(segments[i].f, i));
            pts.pb(mp(segments[i].s, i));
        }
        sort(all(pts));
        vector<vector<pair<int, int>>> graph(segments.size());
        for (int i = 1; i < pts.size(); ++i) {
            graph[dsu.get(pts[i - 1].s)].pb(mp(dsu.get(pts[i].s), pts[i].f - pts[i - 1].f));
            graph[dsu.get(pts[i].s)].pb(mp(dsu.get(pts[i - 1].s), pts[i].f - pts[i - 1].f));
        }
        int start = -1;
        for (int i = 0; i < segments.size(); ++i) {
            if (segments[i].f == s) {
                start = dsu.get(i);
                break;
            }
        }
        priority_queue<pair<int, ll>> q;
        vector<ll> d(segments.size(), 1e18);
        d[start] = 0;
        q.push(mp(0, start));
        vector<int> marked(segments.size());
        while (!q.empty()) {
            int v = q.top().s;
            q.pop();
            if (marked[v]) {
                continue;
            }
            marked[v] = true;
            for (auto &u: graph[v]) {
                if (d[u.f] > d[v] + u.s) {
                    d[u.f] = d[v] + u.s;
                    q.push(mp(d[u.f], u.f));
                }
            }
        }
        int best = -1;
        for (int i = 0; i < segments.size(); ++i) {
            if (segments[i].f <= s && segments[i].s >= s && (best == -1 || segments[best].s - segments[best].f < segments[i].s - segments[i].f)) {
                best = i;
            }
        }
        ans += d[dsu.get(best)] * 2;
    }
    return ans;
}

#ifdef LOCAL
signed main() {
    freopen("in.txt", "r", stdin);
    int n, s;
    cin >> n >> s;
    vector<int> p(n);
    cin >> p;
    int ans = minimum_walk(p, s);
    cout << ans << endl;
}
#endif

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