Submission #293767

#	Time	Username	Problem	Language	Result	Execution time	Memory
293767		shayan_p	Ancient Books (IOI17_books)	C++17	12 / 100	17 ms	12160 KiB

books

// Oh damn! Suddenly you're free to fly...
 
#include<bits/stdc++.h>
#include "books.h"
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int cnt[maxn];

int pr[maxn], L[maxn], R[maxn];

int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
void mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return;
    if(pr[a] > pr[b])
	swap(a, b);
    L[a] = min(L[a], L[b]);
    R[a] = max(R[a], R[b]);
    pr[a]+= pr[b];
    pr[b] = a;	    
}

int par[maxn];

ll minimum_walk(vector<int> p, int s){
    memset(pr, -1, sizeof pr);
    iota(L, L + maxn, 0);
    iota(R, R + maxn, 0);
    
    int n = sz(p);
    ll ans = 0;
    vector<pii> vec;
    for(int i = 0; i < n; i++){
	int l = i, r = p[i];
	if(l > r)
	    swap(l, r);
	ans+= r-l;
	mrg(l, r);
	vec.PB({l, r});
    }
    for(pii p : vec){
	for(pii p2 : vec){
	    if(p.F > p2.F)
		swap(p, p2);
	    if(p.S < p2.S && p2.F < p.S)
		mrg(p.F, p2.F);
	}
    }

    vector<int> seg;
    for(int i = 0; i < n; i++){
	if(i == fnd(i)){
	    seg.PB(i);
	}
    }

    sort(seg.begin(), seg.end(), [&](int i, int j){ return L[i] > L[j]; });

    vector<int> st;
    for(int id : seg){
	while(sz(st) && R[st.back()] <= R[id]){
	    par[st.back()] = id;
	    st.pop_back();
	}
	st.PB(id);
    }

    for(int id : st){
	par[id] = -1;
    }

    int ptl = 0, ptr = sz(st) - 1;
    while(ptl < sz(st) && L[st[ptl]] == R[st[ptl]] && L[st[ptl]] != s)
	ptl++;
    while(ptr >= 0 && L[st[ptr]] == R[st[ptr]] && L[st[ptr]] != s)
	ptr--;
    for(int i = ptl; i < ptr; i++){
	ans+= 2 * (L[st[i]] - R[st[i+1]]);
    }

    int tmp = fnd(s);
    while(par[tmp] != -1){
	int PTL = L[tmp], PTR = R[tmp];
	int _PTL = L[par[tmp]], _PTR = R[par[tmp]];
	int d1 = 0, d2 = 0;
	while(PTL > _PTL){
	    PTL = L[fnd(PTL)];
	    d1++;
	    PTL--;
	}
	while(PTR < _PTR){
	    PTR = R[fnd(PTR)];
	    d2++;
	    PTR++;
	}
	ans+= 2 * min(d1, d2);

	tmp = par[tmp];
    }
    return ans;
}

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