Submission #782264

#	Time	Username	Problem	Language	Result	Execution time	Memory
782264		lukameladze	Ancient Books (IOI17_books)	C++17	100 / 100	780 ms	158056 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pii pair <int, int>
#define pb push_back
const int N = 1e6 + 5,inf = 1e9;
int n, p[N],fix[N],l[N],r[N],cur,pr[N],idx[N],cnt,opp[N];
int tree[3][4 * N];
void build(int node, int le, int ri) {
    if (le == ri) {
        if (opp[le] && opp[le] >= le) tree[0][node] = opp[le];
        if (opp[le] && opp[le] <= le) tree[1][node] = opp[le];
        return ;
    }
    int mid = (le + ri) / 2;
    build(2 * node, le, mid);
    build(2 * node + 1, mid + 1, ri);
    tree[0][node] = max(tree[0][2 * node], tree[0][2 * node + 1]);
    tree[1][node] = min(tree[1][2 * node], tree[1][2 * node + 1]);
}
void update(int node, int le, int ri, int idx, int val, int ty) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        tree[ty][node] = val;
        return ;
    }
    int mid = (le + ri) / 2;
    update(2 * node, le, mid, idx, val, ty);
    update(2 * node + 1, mid + 1, ri, idx, val, ty);
    tree[0][node] = max(tree[0][2 * node], tree[0][2 * node + 1]);
    tree[1][node] = min(tree[1][2 * node], tree[1][2 * node + 1]);
}
int getans(int node, int le, int ri, int start, int end, int ty) {
    if (le > end || ri < start) {
        return (ty == 0 ? -inf : inf);
    }
    if (le >= start && ri <= end) return tree[ty][node];
    int mid = (le + ri) / 2;
    int p1 = getans(2 * node, le, mid, start, end, ty);
    int p2 = getans(2 * node + 1, mid + 1, ri, start, end, ty);
    return (ty == 0 ? max(p1, p2) : min(p1, p2));
}
vector <pii> g[N];
void add_edge(int a, int b, int c) {
    g[a].pb({b, c});
    g[b].pb({a, c});
}
int dist[N];
int bfs01(int s, int l, int r) {
    deque < int > dq;
    for (int i = 1; i <= n; i++) {
        dist[i] = inf;
    }
    dist[s] = 0;
    dq.pb(s);
    while (!dq.empty()) {
        int vert = dq[0];
        if (vert == l || vert == r) return dist[vert];
        dq.pop_front();
        for (pii sth : g[vert]) {
            int to = sth.f, c = sth.s;
            if (dist[to] > dist[vert] + c) {
                dist[to] = dist[vert] + c;
                if (c == 0) dq.push_front(to);
                else dq.push_back(to);
            }
        }
    }
    assert(false);
}
long long minimum_walk(vector<int> perm, int s) {
    s++;
    n = perm.size();
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        p[i] = perm[i - 1] + 1;
        ans += (ll)abs(i - p[i]);
    }

    int frst_id = -1, lst_id = -1;
    for (int i = 1; i <= n ;i++) {
        if (p[i] != i && frst_id == -1) frst_id = i;
        if (p[i] != i) lst_id = i;
    }
    if (frst_id == -1) {
        return 0;
    }
    vector <pii> segs;
    for (int i = 1; i <= n; i++) {
        int cur = p[i];
        if (!fix[i]) {
            fix[i] = 1;
            idx[i] = ++cnt;
            l[cnt] = r[cnt] = i;
            vector <int> vec;
            vec.pb(i);
            while (cur != i) {
                vec.pb(cur);
                fix[cur] = 1;
                l[cnt] = min(l[cnt], cur);
                r[cnt] = max(r[cnt], cur);
                cur = p[cur];
            }
            sort(vec.begin(), vec.end());
            for (int i = 1; i < (int)vec.size(); i++) {
                add_edge(vec[i], vec[i - 1], 0);
                segs.pb({vec[i - 1], vec[i]});
            }
            opp[l[cnt]] = r[cnt];
            opp[r[cnt]] = l[cnt];
            pr[l[cnt]]++;
            pr[r[cnt]]--;
        }
    }
    for (int i = 1; i <= n; i++) {
        pr[i] += pr[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        if (pr[i] == 0 && i < lst_id && i >= frst_id) ans += 2;
        else {
            if (pr[i] == 0 && s <= i && i < lst_id) ans += 2;
            else if (pr[i] == 0 && s > i && i >= frst_id) ans += 2;
        }
    }
    for (int i = 1; i < n; i++) {
        add_edge(i, i + 1, 1);
    }
    int posi = s, posj = s;
    sort(segs.begin(), segs.end());
    build(1, 1, n);
    for (pii sth : segs) {
        int l = sth.f, r = sth.s;
        // Left E [l + 1, r - 1]   maximum Right
        int mx = getans(1, 1, n, l + 1, r - 1, 0);
        if (mx > r) {
            add_edge(l, mx, 0);
        }
        // Right E [l + 1, r - 1], minimum left 
        int mn = getans(1, 1, n, l + 1, r - 1, 1);
        if (mn < l) {
            add_edge(r, mn, 0);
        }
    }
    int lid = 1, rid = n;
    for (int i = 0; i < s; i++) {
        if (!pr[i]) lid = i + 1;
    }
    for (int i = s; i <= n; i++) {
        if (!pr[i]) { rid = i; break; }
    }
    int to_add = bfs01(s, lid, rid);
    ans += (ll)2 * (ll)to_add;
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:131:9: warning: unused variable 'posi' [-Wunused-variable]
  131 |     int posi = s, posj = s;
      |         ^~~~
books.cpp:131:19: warning: unused variable 'posj' [-Wunused-variable]
  131 |     int posi = s, posj = s;
      |                   ^~~~

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