Submission #125064

#	Time	Username	Problem	Language	Result	Execution time	Memory
125064		nvmdava	Ancient Books (IOI17_books)	C++17	100 / 100	165 ms	8440 KiB

books

#include <bits/stdc++.h>
using namespace std;
long long res;
 
inline void push(int& l, int& r, int& mn, int& mx, vector<int>& p){
   while(l != mn || r != mx){
      if(l != mn){
         l--;
         mn = min(mn, p[l]);
         mx = max(mx, p[l]);
      } else {
         r++;
         mn = min(mn, p[r]);
         mx = max(mx, p[r]);
      }
   }
}
long long minimum_walk(vector<int> p, int s){
   int L = 0, R = p.size() - 1;
   while(R >= 0 && p[R] == R) R--;
   if(R == -1) return 0;
   while(p[L] == L) L++;
 
   if(s > R){
      res += (s - R) << 1;
      s = R;
   }
   if(s < L){
      res += (L - s) << 1;
      s = L;
   }
 
   int tmn = s, tmx = s;
   for(int i = L; i <= R; i++){
      res += abs(p[i] - i);
      if(1LL * (tmx - p[i]) * (tmx - i) <= 0 || 1LL * (tmn - p[i]) * (tmn - i) <= 0){
         tmx = max(tmx, max(i, p[i]));
         tmn = min(tmn, min(i, p[i]));
      }
   }
   int l, r, mn = min(s, p[s]), mx = max(s, p[s]);
   l = r = s;
   push(l, r, tmn, tmx, p);
 
   l = r = s;
   push(l, r, mn, mx, p);
 
   while(mn != tmn || mx != tmx){
      res += 2;
      if(mn != tmn)mn--;
      if(mx != tmx)mx++;
      push(l, r, mn, mx, p);
   }
   for(; l >= L; l--){
      if(mn > l) res += 2;
      mn = min(mn, p[l]);
   }
   for(; r <= R; r++){
      if(mx < r) res += 2;
      mx = max(mx, p[r]);
   }
   return res;
}

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