Submission #1011791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011791		c2zi6	Ancient Books (IOI17_books)	C++14	70 / 100	492 ms	103352 KiB

books

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "books.h"

template<int BASE, typename COMP>
struct SEGTREE {
    int n;
    VPI tree;
    COMP COMPOBJ;
    SEGTREE(int sz) {
        n = 1;
        while (n < sz) n *= 2;
        tree = VPI(2*n, {BASE, -1});
    }
    PII lav(PII a, PII b) {
        if (COMPOBJ(a, b)) return a;
        return b;
    }
    void upd(int N, int L, int R, int i, PII s) {
        if (i < L || i > R) return;
        if (L == R) {
            tree[N] = s;
            return;
        }
        int M = (L + R) / 2;
        upd(2*N+1, L, M, i, s);
        upd(2*N+2, M+1, R, i, s);
        tree[N] = lav(tree[2*N+1], tree[2*N+2]);
    }
    PII get(int N, int L, int R, int l, int r) {
        if (l <= L && R <= r) return tree[N];
        if (R < l || L > r) return {BASE, -1};
        int M = (L + R) / 2;
        return lav(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
    }
    void upd(int i, PII s) {
        upd(0, 0, n-1, i, s);
    }
    PII get(int l, int r) {
        if (l > r) return {BASE, -1};
        return get(0, 0, n-1, l, r);
    }
};

namespace TEST5 {
    int s;
    VI p;
    VI vis, group;
    ll ans;
    map<PII, VI> comps;
    PII getcomp(int s) {
        PII ret{s, s};
        int u = s;
        VI vec;
        do {
            vec.pb(u);
            vis[u] = true;
            setmin(ret.ff, u);
            setmax(ret.ss, u);
            ans += abs(p[u]-u);
            u = p[u];
        } while (u != s);
        for (int u : vec) comps[ret].pb(u);
        return ret;
    }
    PII skizbp;
    void compressranges(VPI& ranges) {
        int n = ranges.size();
        VI vis(n);
        function<void(int)> dfs;
        VI comp;
        SEGTREE<(int)-2e9, greater<PII>> mxval(p.size());
        SEGTREE<(int)+2e9, less<PII>> mnval(p.size());
        rep(i, n) {
            auto[l, r] = ranges[i];
            mxval.upd(l, {r, i});
            /*cout << "AT " << l << " SAT {" << r << ", " << i << "}" << endl;*/
            mnval.upd(r, {l, i});
        }
        /*cout << "NOW PRINTING THE GRAPH" << endl;*/
        VVI gp(n);
        rep(u, n) {
            auto[l, r] = ranges[u];
            PII p1 = mxval.get(l+1, r-1);
            if (p1.ff > r) {
                gp[u].pb(p1.ss);
                gp[p1.ss].pb(u);
            }
            PII p2 = mnval.get(l+1, r-1);
            if (p2.ff < l) {
                gp[u].pb(p2.ss);
                gp[p2.ss].pb(u);
            }
        }
        /*cout << "ENDED" << endl;*/
        dfs = [&](int u) {
            comp.pb(u);
            vis[u] = true;
            VI harevan;
            for (int v : gp[u]) if (!vis[v]) {
                dfs(v);
            }
        };
        if (true) {
            VPI tmp;
            rep(u, n) if (!vis[u]) {
                comp.clear();
                dfs(u);
                PII ret = {+2e9, -2e9};
                for (int u : comp) {
                    setmin(ret.ff, ranges[u].ff);
                    setmax(ret.ss, ranges[u].ss);
                }
                VI vec;
                for (int u : comp) {
                    for (int x : comps[ranges[u]]) {
                        vec.pb(x);
                    }
                }
                comps[ret].clear();
                for (int x : vec) comps[ret].pb(x);
                if (u == 0) skizbp = ret;
                tmp.pb(ret);
            }
            ranges = tmp;
        }
        sort(all(ranges));
        PII glxavor = {s, s};
        int cur = -1;
        VPI roots;
        while (true) {
            auto it = upper_bound(all(ranges), PII{cur, +2e9});
            if (it == ranges.end()) break;
            roots.pb(*it);
            if (it->ff <= s && s <= it->ss) {
                glxavor = *it;
            }
            cur = it->ss;
        }
        replr(i, 1, roots.size()-1) {
            ans += (roots[i].ff - roots[i-1].ss)*2;
        }

        VPI tmp{glxavor};
        for (PII p : ranges) {
            if (glxavor.ff < p.ff && p.ss < glxavor.ss) {
                tmp.pb(p);
            }
        }
        ranges = tmp;
    }
    ll solve(VI PARG, int SARG) {p = PARG, s = SARG;
        VPI ranges;
        vis = VI(p.size());
        group = VI(p.size(), -1);
        ranges.pb(getcomp(s));
        rep(u, p.size()) if (u != p[u] && !vis[u]) ranges.pb(getcomp(u));
        /*int q;*/
        /*cin >> q;*/
        /*while (q--) {*/
        /*    int l, r;*/
        /*    cin >> l >> r;*/
        /*    ranges.pb({l, r});*/
        /*}*/
        compressranges(ranges);
        sort(all(ranges), [&](PII a, PII b){
                    swap(a.ff, a.ss);
                    swap(b.ff, b.ss);
                    return a < b;
                });
        int n = ranges.size();
        VPI points;
        rep(i, n) {
            for (int x : comps[ranges[i]]) {
                points.pb({x, i});
            }
        }
        sort(all(points));
        VVPI gp(n);
        rep(u, n) {
            auto[l, r] = ranges[u];
            VPI::iterator(it);
            it = upper_bound(all(points), PII{r, +2e9});
            if (it != points.end()) {
                gp[u].pb({it->ss, (it->ff-r)*2});
            }
            it = lower_bound(all(points), PII{l, -2e9});
            if (it != points.begin()) {it--;
                gp[u].pb({it->ss, (l-it->ff)*2});
            }
        }

        int start = -1;
        rep(i, n) if (ranges[i] == skizbp) start = i;

        priority_queue<PLL> pq;
        VL dist(n, 1e18);
        VI vis(n);
        pq.push({0, start});
        dist[start] = 0;
        while (pq.size()) {
            int u = pq.top().ss;
            pq.pop();
            if (vis[u]) continue;
            vis[u] = true;
            for (auto[v, w] : gp[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({-dist[v], v});
                }
            }
        }

        return ans + dist.back();
    }
}

namespace TEST4 {
    int s;
    VI p;
    VI vis, group;
    ll ans;
    map<PII, VI> comps;
    PII getcomp(int s) {
        PII ret{s, s};
        int u = s;
        VI vec;
        do {
            vec.pb(u);
            vis[u] = true;
            setmin(ret.ff, u);
            setmax(ret.ss, u);
            ans += abs(p[u]-u);
            u = p[u];
        } while (u != s);
        for (int u : vec) comps[ret].pb(u);
        return ret;
    }
    PII skizbp;
    void compressranges(VPI& ranges) {
        int n = ranges.size();
        VI vis(n);
        function<void(int)> dfs;
        VI comp;
        dfs = [&](int u) {
            comp.pb(u);
            vis[u] = true;
            rep(v, n) if (!vis[v]) {
                if (ranges[v].ss < ranges[u].ff || ranges[v].ff > ranges[u].ss) continue;
                if (ranges[u].ff < ranges[v].ff && ranges[v].ss < ranges[u].ss) continue;
                if (ranges[v].ff < ranges[u].ff && ranges[u].ss < ranges[v].ss) continue;
                dfs(v);
            }
        };
        if (true) {
            VPI tmp;
            rep(u, n) if (!vis[u]) {
                comp.clear();
                dfs(u);
                PII ret = {+2e9, -2e9};
                for (int u : comp) {
                    setmin(ret.ff, ranges[u].ff);
                    setmax(ret.ss, ranges[u].ss);
                }
                VI vec;
                for (int u : comp) {
                    for (int x : comps[ranges[u]]) {
                        vec.pb(x);
                    }
                }
                comps[ret].clear();
                for (int x : vec) comps[ret].pb(x);
                if (u == 0) skizbp = ret;
                tmp.pb(ret);
            }
            ranges = tmp;
        }
        sort(all(ranges));
        PII glxavor = {s, s};
        int cur = -1;
        VPI roots;
        while (true) {
            auto it = upper_bound(all(ranges), PII{cur, +2e9});
            if (it == ranges.end()) break;
            roots.pb(*it);
            if (it->ff <= s && s <= it->ss) {
                glxavor = *it;
            }
            cur = it->ss;
        }
        replr(i, 1, roots.size()-1) {
            ans += (roots[i].ff - roots[i-1].ss)*2;
        }

        VPI tmp{glxavor};
        for (PII p : ranges) {
            if (glxavor.ff < p.ff && p.ss < glxavor.ss) {
                tmp.pb(p);
            }
        }
        ranges = tmp;
    }
    ll solve(VI PARG, int SARG) {p = PARG, s = SARG;
        VPI ranges;
        vis = VI(p.size());
        group = VI(p.size(), -1);
        ranges.pb(getcomp(s));
        rep(u, p.size()) if (u != p[u] && !vis[u]) ranges.pb(getcomp(u));
        compressranges(ranges);
        sort(all(ranges), [&](PII a, PII b){
                    swap(a.ff, a.ss);
                    swap(b.ff, b.ss);
                    return a < b;
                });
        int n = ranges.size();
        VPI points;
        rep(i, n) {
            for (int x : comps[ranges[i]]) {
                points.pb({x, i});
            }
        }
        sort(all(points));
        VVPI gp(n);
        rep(u, n) {
            auto[l, r] = ranges[u];
            VPI::iterator(it);
            it = upper_bound(all(points), PII{r, +2e9});
            if (it != points.end()) {
                gp[u].pb({it->ss, (it->ff-r)*2});
            }
            it = lower_bound(all(points), PII{l, -2e9});
            if (it != points.begin()) {it--;
                gp[u].pb({it->ss, (l-it->ff)*2});
            }
        }

        int start = -1;
        rep(i, n) if (ranges[i] == skizbp) start = i;

        priority_queue<PLL> pq;
        VL dist(n, 1e18);
        VI vis(n);
        pq.push({0, start});
        dist[start] = 0;
        while (pq.size()) {
            int u = pq.top().ss;
            pq.pop();
            if (vis[u]) continue;
            vis[u] = true;
            for (auto[v, w] : gp[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({-dist[v], v});
                }
            }
        }

        return ans + dist.back();
    }
}


ll minimum_walk(VI p, int s) {
    return TEST5::solve(p, s);
}

Compilation message (stderr)

books.cpp: In function 'void TEST5::compressranges(VPI&)':
books.cpp:104:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |             auto[l, r] = ranges[i];
      |                 ^
books.cpp:112:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |             auto[l, r] = ranges[u];
      |                 ^
books.cpp: In function 'll TEST5::solve(VI, int)':
books.cpp:210:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  210 |             auto[l, r] = ranges[u];
      |                 ^
books.cpp:211:26: warning: unnecessary parentheses in declaration of 'it' [-Wparentheses]
  211 |             VPI::iterator(it);
      |                          ^
books.cpp:235:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  235 |             for (auto[v, w] : gp[u]) {
      |                      ^
books.cpp: In function 'll TEST4::solve(VI, int)':
books.cpp:354:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  354 |             auto[l, r] = ranges[u];
      |                 ^
books.cpp:355:26: warning: unnecessary parentheses in declaration of 'it' [-Wparentheses]
  355 |             VPI::iterator(it);
      |                          ^
books.cpp:379:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  379 |             for (auto[v, w] : gp[u]) {
      |                      ^

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