제출 #638815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638815		qwerasdfzxcl	고대 책들 (IOI17_books)	C++17	100 / 100	643 ms	180004 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int  n, s, ts, ans, a[1001000], cycL[1001000], cycR[1001000], L[1001000], R[1001000], dp[1001000];
bool visited[1001000];
ll cycsum;

struct Seg{
    int tree[2002000], sz;
    void init(int n){
        sz = n;
        fill(tree, tree+sz*2, 1e9);
    }
    void update(int p, int x){
        for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]);
    }
    int query(int l, int r){
        int ret = 1e9;
        ++r;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
}tree1, tree2;

ll myabs(ll x){
    if (x<0) return -x;
    return x;
}


void dfs(int l, int r){
    //printf("dfs: %d %d\n", l, r);
    if (l==L[ts] && r==R[ts]) {ans += dp[L[ts]]; return;}

    vector<pair<int, int>> child;
    for (int i=l+1;i<r;){
        if (R[i]<r){
            child.emplace_back(i, R[i]);
            i = R[i] + 1;
        }
        else i++;
    }

    vector<int> gl = {1}, gr = {1};
    for (int i=1;i<(int)child.size();i++){
        if (child[i-1].second+1==child[i].first) gl.push_back(gl.back()+1);
        else gl.push_back(1);
    }
    for (int i=(int)child.size()-2;i>=0;i--){
        if (child[i].second+1==child[i+1].first) gr.push_back(gr.back()+1);
        else gr.push_back(1);
    }
    reverse(gr.begin(), gr.end());

    for (int i=0;i<(int)child.size();i++) dp[child[i].first] = min(gl[i], gr[i]) + dp[l];
    if (l==0) for (int i=0;i<(int)child.size();i++) dp[child[i].first] = (int)child.size()-1;

    for (auto &[nl, nr]:child) dfs(nl, nr);
}

map<pair<int, int>, int> mp;
void naive(int s){
    int ptl = s, ptr = s;
    while(true){
        int nl = tree1.query(ptl, ptr);
        int nr = -tree2.query(ptl, ptr);

        if (nl==ptl && nr==ptr) {L[s] = nl, R[s] = nr; break;}
        if (mp.find(make_pair(nl, nr))!=mp.end()) {
            int tmp = mp[make_pair(nl, nr)];
            L[s] = L[tmp], R[s] = R[tmp];
            break;
        }

        mp[make_pair(nl, nr)] = s;
        ptl = nl, ptr = nr;

    }
}

long long minimum_walk(std::vector<int> P, int S) {
    int si = 0, ei = (int)P.size()-1;
    for(;si<(int)P.size() && P[si]==si;si++);
    for(;ei>=0 && P[ei]==ei;ei--);

    if (si > ei) return 0;
    n = ei-si+1;
    for (int i=si;i<=ei;i++) a[i-si+1] = P[i] - si + 1;
    s = S-si+1;

    tree1.init(n+1);
    tree2.init(n+1);
    for (int i=1;i<=n;i++) if (!visited[i]){
        vector<int> cyc;

        for (int j=i;!visited[j];j=a[j]){
            cyc.push_back(j);
            visited[j] = 1;
            cycR[i] = max(cycR[i], j);
            cycsum += myabs(j - a[j]);
        }
        cycL[cycR[i]] = i;

        for (auto &x:cyc){
            tree1.update(x, i);
            tree2.update(x, -cycR[i]);
        }
    }

    ///calc range
    for (int i=1;i<=n;i++) naive(i);

    /*for (int i=1;i<=n;i++) printf("(%d, %d) ", cycL[i], cycR[i]);
    printf("\n");
    for (int i=1;i<=n;i++) printf("(%d, %d) ", L[i], R[i]);
    printf("\n");*/

    if (s<=0) ts = 1, ans = 1-s;
    else if (s>n) ts = n, ans = s-n;
    else ts = s, ans = 0;

    //printf("ok n = %d, s = %d\n", n, s);
    dfs(0, n+1);

    //printf("%lld + %d * 2\n", cycsum, ans);
    return cycsum + ans * 2;
}

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