제출 #297026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297026		shayan_p	고대 책들 (IOI17_books)	C++17	50 / 100	196 ms	18808 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 go = [&](){
		  while(true){
		      bool is = 0;
		      while(r < n && r <= MX){
			  MX = max(MX, p[r]);
			  r++;
			  is = 1;
		      }
		      while(l >= 0 && l >= MN){
			  MN = min(MN, p[l]);
			  l--;
			  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;
	l--, r++;
	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: 0 / 20
• Subtask 5: 0 / 30