제출 #295721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295721		shayan_p	Ancient Books (IOI17_books)	C++17	12 / 100	2091 ms	16128 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 pr[maxn], L[maxn], R[maxn];
int pr2[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;	    
}
 
ll minimum_walk(vector<int> p, int s){
    memset(pr, -1, sizeof pr);
    memset(pr2, -1, sizeof pr2);

    iota(L, L + maxn, 0);
    iota(R, R + maxn, 0);
    
    int n = sz(p);
    ll ans = 0;
 
    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);
    }
    vector<int> vec;
    for(int i = 0; i < n; i++){
	if(fnd(i) == i)
	    vec.PB(i);
    }
    sort(vec.begin(), vec.end(), [&](int i, int j){ return L[fnd(i)] > L[fnd(j)]; });
    int LST = n-1;
    for(int id : vec){
	int tmp = R[fnd(id)];
	while(LST >= L[fnd(id)]){
	    if(LST != id)
		pr2[LST] = id;
	    LST--;
	}
	while(tmp != -1){
	    mrg(id, tmp);
	    int nx = pr2[tmp];
	    pr2[tmp] = id;
	    tmp = nx;
	}
    }
    
    int l = s, r = s;
    while(true){
	while(true){
	    bool is = 0;
	    while(r < R[fnd(s)])
		mrg(s, ++r), is = 1;
	    while(l > L[fnd(s)])
		mrg(s, --l), is = 1;
	    if(!is)
		break;
	}
	int d1 = 0, d2 = 0;
	while(r < n && L[fnd(s)] <= L[fnd(r)]){
	    d2+= R[fnd(s)] < r;
	    mrg(s, r);
	    r++;
	}
	while(l >= 0 && R[fnd(l)] <= R[fnd(s)]){
	    d1+= L[fnd(s)] > l;
	    mrg(s, l);
	    l--;
	}
	if(l == -1 || r == n){
	    assert(l == -1 && r == n);
	    ans+= 2 * (d1 + d2);
	    break;
	}
	else{
	    ans+= 2 * min(d1 + 1, d2 + 1);
	    //	    assert(fnd(l) == fnd(r));
	    mrg(s, l);
	    mrg(s, r);
	}	    
    }
    for(int i = 0; i < s && p[i] == i; i++){
	ans-= 2;
    }
    for(int i = n-1; i > s && p[i] == i; i--){
	ans-= 2;
    }
    return ans;
}

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