Submission #42759

#	Time	Username	Problem	Language	Result	Execution time	Memory
42759		yusufake	Ancient Books (IOI17_books)	C++98	100 / 100	269 ms	169312 KiB

books

#include<bits/stdc++.h>
 
using namespace std;
 
#define _   int v, int tl, int tr, int l, int r
#define tm  (tl+tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r
 
#define mp make_pair
#define pb push_back
#define st first
#define nd second
 
//typedef long long ll;
//typedef pair < ll , ll > pp;
 
const int mod = 1e9 + 7;
const int N   = 1e6 + 6;
 
int H[N],T[N],A[N],B[N],n,i,j,l,r,ll,rr,t1,t2,t,a,b,lll,rrr;
long long x;
 
void relax(int &l, int &r, int &a, int &b){
    for(;l > a || r < b;){
        if(l > a) { l--; a = min(a,A[l]); b = max(b,B[l]); }
        if(r < b) { r++; a = min(a,A[r]); b = max(b,B[r]); }
    }
}
 
long long minimum_walk(vector < int > p, int s){
    x = 0;
    n = p.size();
	for(i=0;i<n;i++){
		x += abs(p[i] - i);
		if(H[i]) continue;
		r = i;
		for(j=i; !H[j] ; j = p[j]){
			H[j] = 1;
			r = max(r , j);
		}
        for(j=i; !T[j] ; j = p[j]){
		    T[j] = 1; A[j] = i; B[j] = r;
        }
    }
    
    for(i=0;i<n && p[i] == i; i++);
    for(j=n-1;j>=0 && p[j] == j; j--);
    
    l = r = s; a = A[s]; b = B[s];
    relax(l,r,a,b);
    for(; l > i || r < j ;){
        t1 = 0;
        ll = lll = l; rr = rrr = r;
        if(l > i){
            for(a=l, b=r ; rr == r && ll > i ; )
            { ll--; t1++; a = min(A[ll],a); b = max(B[ll],b); relax(ll,rr,a,b); }    
            if(r >= j) { t += t1; break; }
        }
        
        t2 = 0;
        if(r < j){
            for(a = l, b = r ; lll == l && rrr < j ; )
            { rrr++; t2++; a = min(A[rrr],a); b = max(B[rrr],b); relax(lll,rrr,a,b); }    
            if(l <= i) { t += t2; break; }
        }
        if(rr == r) { if(lll != l) assert(0);  t += t1+t2; break; }
        t += min(t1,t2);
        l = ll; r = rr;
        if(lll != ll || rrr != rr) assert(0);
    }
    
    return x + t+t;
}
/*
int main(){
    cout << minimum_walk({1,0,2,3} , 2);
} */

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