Submission #1095326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095326		epicci23	Text editor (CEOI24_editor)	C++17	100 / 100	827 ms	464724 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,a,b,c,d;
  cin >> n >> a >> b >> c >> d;
  vector<int> pre(n+5),suf(n+5),ar(n+5);
  int Sparse[n+5][20];
  for(int i=1;i<=n;i++){
  	cin >> ar[i];
  	ar[i]++;
    Sparse[i][0]=ar[i];
  }
  for(int j=1;j<20;j++){
   for(int i=1;i+(1<<j)-1<=n;i++){
    Sparse[i][j]=min(Sparse[i][j-1],Sparse[i+(1<<(j-1))][j-1]);
   }
  }
  
  auto Get=[&](int l,int r)->int {
    if(l>r) swap(l,r);
    int k=__lg(r-l+1);
    return min(Sparse[l][k],Sparse[r-(1<<k)+1][k]);
  };

  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));
    }
  }


  priority_queue<array<int,2>> pq;
  vector<int> dist(2*n+5,INF),vis(2*n+5,0);
  vector<array<int,2>> v[2*n+5];
  int st=2*n+1,en=2*n+2;

  v[st].push_back({2*a-1,b-1});
  v[st].push_back({2*a,ar[a]-b});
  v[2*a-1].push_back({st,b-1});
  v[2*a].push_back({st,ar[a]-b});

  v[en].push_back({2*c-1,d-1});
  v[en].push_back({2*c,ar[c]-d});
  v[2*c-1].push_back({en,d-1});
  v[2*c].push_back({en,ar[c]-d});

  for(int i=1;i<=n;i++){
    v[2*i].push_back({2*i-1,ar[i]-1});
    v[2*i-1].push_back({2*i,ar[i]-1});
    if(i<n){
      v[2*i].push_back({2*i+1,1});
      v[2*i+1].push_back({2*i,1});
      v[2*i-1].push_back({2*i+1,1});
      v[2*i+1].push_back({2*i-1,1});
      if(ar[i]<=ar[i+1]){
        v[2*i].push_back({2*i+2,1+ar[i+1]-ar[i]});
        v[2*i+2].push_back({2*i,1});
      }
      else{
        v[2*i].push_back({2*i+2,1});
        v[2*i+2].push_back({2*i,1+ar[i]-ar[i+1]});
      }
    }
  }

  for(int i=1;i<=n;i++){
    if(Get(a,i)<=b && ar[i]==Get(a,i)) v[st].push_back({2*i,abs(a-i)});
  }

  dist[st]=0;
  pq.push({0,st});

  while(!pq.empty()){
    int c=pq.top()[1];
    pq.pop();
    if(vis[c]) continue;
    vis[c]=1;
    for(auto [u,d]:v[c]){
      if(!vis[u] && d+dist[c]<dist[u]){
        dist[u]=d+dist[c];
        pq.push({-dist[u],u});
      }
    }
  }

  ans=min(ans,dist[en]);
  for(int i=1;i<=n;i++){
    if(Get(i,c)==ar[i]) ans=min(ans,dist[2*i]+abs(c-i)+abs(d-ar[i]));
  }

  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: 14 / 14
• Subtask 3: 26 / 26
• Subtask 4: 11 / 11
• Subtask 5: 44 / 44