Submission #297037

#	Time	Username	Problem	Language	Result	Execution time	Memory
297037		shayan_p	Ancient Books (IOI17_books)	C++17	100 / 100	196 ms	18872 KiB

books

#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;
     
int cnt[maxn];
     
ll minimum_walk(vector<int> p, int s){
    int n = sz(p);
        
    int MN = s, MX = s;
    ll ans = 0;
    for(int i = 0; i < n; i++){
    	ans+= abs(p[i] - i);
    	cnt[min(i, p[i])]++;
    	cnt[max(i, p[i])]--;
    }
    int l = s, r = s;

    auto forw = [&]{
		    MX = max(MX, p[r]);
		    MN = min(MN, p[r]);
		    r++;
		};
    auto backw = [&]{
		     MN = min(MN, p[l]);
		     MX = max(MX, p[l]);
		     l--;
		 };
    auto go = [&](){
    		  while(true){
    		      bool is = 0;
    		      while(r < n && r <= MX)			  
    			  forw(), is = 1;
    		      while(l >= 0 && l >= MN)
    			  backw(), is = 1;
    		      if(!is)
    			  break;
    		  }
    	      };
    int L = -1, R = n;
    int lst = -1;
    int sm = 0;
    for(int i = 0; i < n; i++){
    	sm+= cnt[i];
    	if(sm == 0){
    	    if(i != n-1)
    		ans+= 2;
    	    if(lst < s && s <= i)
    		L = lst, R = i+1;
    	    lst = i;
    	}	
    }
     
    go();
    while(L < l || r < R){
    	ans+= 2;
	backw(), forw();
    	go();
    }
    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: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30