Submission #1095298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095298		epicci23	Text editor (CEOI24_editor)	C++17	16 / 100	114 ms	73808 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e18;

void _(){
  int n;
  int a,b,c,d;
  cin >> n >> a >> b >> c >> d;
  vector<int> pre(n+5),suf(n+5),ar(n+5);
  for(int i=1;i<=n;i++){
  	cin >> ar[i];
  	ar[i]++;
  }
  pre[a]=suf[a]=b;
  
  for(int i=a-1;i>=1;i--) pre[i]=min(pre[i+1],ar[i]);
  for(int i=a+1;i<=n;i++) suf[i]=min(suf[i-1],ar[i]);

  int ans=INF;
  
  if(a<=c){
    for(int i=a;i>=1;i--){
      ans=min(ans,a-i+c-i+abs(min(pre[i],suf[c])-d));
    }
  } 
  else{
    for(int i=a;i<=n;i++){
      ans=min(ans,i-a+i-c+abs(min(suf[i],pre[c])-d));
    }
  }
  
  vector<array<int,2>> dp_s(n+5,{INF,INF});
  vector<array<int,2>> dp_t(n+5,{INF,INF});
  for(int i=a;i>=1;i--){
    dp_s[i][0]=min(dp_s[i][0],a-i+abs(pre[i]-1));
    dp_s[i][1]=min(dp_s[i][1],a-i+abs(pre[i]-ar[i]));
  }
  for(int i=a;i<=n;i++){
  	dp_s[i][0]=min(dp_s[i][0],i-a+abs(suf[i]-1));
  	dp_s[i][1]=min(dp_s[i][1],i-a+abs(suf[i]-ar[i]));
  }
  
  int p=a+1;
  vector<int> lol(n+5,INF);
  for(int i=a;i<=n;i++){
    while(p>1 && suf[i]<=pre[p-1]) p--;
    if(p<=a) lol[p]=min(lol[p],2*i+suf[i]);
  }
  for(int i=1;i<=a;i++) lol[i]=min(lol[i],lol[i-1]);
  for(int i=1;i<=a;i++) dp_s[i][0]=min(dp_s[i][0],lol[i]-a-i-1);
  
  
  p=a-1;
  lol.assign(n+5,INF);
  for(int i=a;i>=1;i--){
    while(p+1<=n && pre[i]<=suf[p+1]) p++;
    if(p>=a) lol[p]=min(lol[p],-2*i+pre[i]);
  }
  for(int i=n;i>=a;i--) lol[i]=min(lol[i],lol[i+1]);
  for(int i=a;i<=n;i++) dp_s[i][0]=min(dp_s[i][0],lol[i]+a+i-1);
   
  p=a-1;
  lol.assign(n+5,INF);
  for(int i=a;i<=n;i++){
    while(p<i && suf[i]<suf[p+1]) p++;
    if(p>=a) lol[p]=min(lol[p],2*i+suf[i]);
  }
  for(int i=n;i>=a;i--) lol[i]=min(lol[i],lol[i+1]);
  for(int i=a;i<=n;i++) dp_s[i][0]=min(dp_s[i][0],lol[i]-a-i-1);
  
  p=a+1;
  lol.assign(n+5,INF);
  for(int i=a;i>=1;i--){
   while(p>i && pre[i]<pre[p-1]) p--;
   if(p<=a) lol[p]=min(lol[p],pre[i]-i);
  }

  for(int i=1;i<=a;i++) lol[i]=min(lol[i],lol[i-1]);
  for(int i=1;i<=a;i++) dp_s[i][0]=min(dp_s[i][0],lol[i]+2*a-i-1);

  swap(a,c),swap(b,d);
  
  
  for(int i=1;i<=n;i++) dp_t[i][0]=abs(b-1)+abs(i-a);
 
  pre[a]=suf[a]=ar[a];
  for(int i=a-1;i>=1;i--) pre[i]=min(pre[i+1],ar[i]);
  for(int i=a+1;i<=n;i++) suf[i]=min(suf[i-1],ar[i]);
  
  for(int i=1;i<=n;i++){
    if(i<=a) dp_t[i][1]=abs(i-a)+abs(pre[i]-b);
    else dp_t[i][1]=abs(i-a)+abs(suf[i]-b);
  }
 
  p=1;
  for(int i=a;i<=n;i++){
   while(p<a && i+a-2*p+abs(b-min(suf[i],pre[p])) >= i+a-2*(p+1)+abs(b-min(suf[i],pre[p+1]))){
     p++;
   }
   dp_t[i][1]=min(dp_t[i][1],i+a-2*p+abs(b-min(suf[i],pre[p])));
  }
 
  p=n;
  for(int i=a;i<=n;i++){
   while(p>i && p>a && 2*p-i-a+abs(b-suf[p]) >= 2*(p-1)-i-a+abs(b-suf[p-1])){
     p--;
   }
   if(p<i) p=i;
   dp_t[i][1]=min(dp_t[i][1],2*p-i-a+abs(b-suf[p]));
  }
 
  p=n;
  for(int i=a;i>=1;i--){
   while(p>a && 2*p-i-a+abs(b-min(pre[i],suf[p])) >= 2*(p-1)-i-a+abs(b-min(pre[i],suf[p-1]))){
     p--;
   }
   dp_t[i][1]=min(dp_t[i][1],2*p-i-a+abs(b-min(pre[i],suf[p])));
  }
 
  p=1;
  for(int i=a;i>=1;i--){
   while(p<i && i+a-2*p+abs(b-pre[p]) >= i+a-2*(p+1)+abs(b-pre[p])){
     p++;
   }
   if(p>i) p=i;
   dp_t[i][1]=min(dp_t[i][1],i+a-2*p+abs(b-pre[p]));
  }

  


  /*for(int i=1;i<=n;i++){
    cout << "i: " << i << '\n';
    cout << "start: " << dp_s[i][0] << ' ' << dp_s[i][1] << '\n';
    cout << "end: " << dp_t[i][0] << ' ' << dp_t[i][1] << '\n';
  }*/

  
  for(int i=1;i<=n;i++){
    if(i>1) ans=min(ans,dp_s[i][0]+1+dp_t[i-1][1]);
    if(i+1<=n) ans=min(ans,dp_s[i][1]+1+dp_t[i+1][0]);
  }

  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 26
• Subtask 4: 11 / 11
• Subtask 5: 0 / 44