oj.uz

Submission #1095304

# Submission time Handle Problem Language Result Execution time Memory
1095304 2024-10-01T20:07:32 Z epicci23 Text editor (CEOI24_editor) C++17
5 / 100
 4000 ms 63940 KB 
#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++){
    for(int j=1;j<=n;j++){
      int cur=abs(i-j)+abs(j-a);
      if(i<=a && j<=a) cur+=abs(b-min(pre[i],pre[j]));
      else if(i<=a && j>a) cur+=abs(b-min(pre[i],suf[j]));
      else if(j<=a) cur+=abs(b-min(suf[i],pre[j]));
      else cur+=abs(b-min(suf[i],suf[j]));
      dp_t[i][1]=min(dp_t[i][1],cur);
    }
  }

  /*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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 524 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Incorrect 2 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 2 ms 524 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Incorrect 2 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 524 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 520 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 1 ms 456 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Execution timed out 4074 ms 63940 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 2 ms 524 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Incorrect 2 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -