Submission #1079524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079524		huutuan	Text editor (CEOI24_editor)	C++14	100 / 100	355 ms	198524 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e6+10, LG=20;
int n, sl, sc, el, ec, a[N], st[LG][N];

int get(int l, int r){
   if (l>r) swap(l, r);
   int lg=__lg(r-l+1);
   return min(st[lg][l], st[lg][r-(1<<lg)+1]);
}

int move(int &x, int &y, int z, int t){
   if (x+1==z && y==a[x]+1 && t==1){
      x=z, y=t;
      return 1;
   }
   if (z+1==x && t==a[z]+1 && y==1){
      x=z, y=t;
      return 1;
   }
   int ans=abs(x-z);
   y=min(get(x, z), y);
   x=z;
   if (t==-1) return ans;
   ans+=abs(y-t); y=t;
   return ans;
}

int calc(int x, int y, vector<pair<int, int>> path){
   int ans=0;
   for (auto &i:path){
      ans+=move(x, y, i.first, i.second);
   }
   return ans;
}

int val1[N], val2[N];
int pf[N], sf[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> sl >> sc >> el >> ec;
   for (int i=1; i<=n; ++i) cin >> a[i], st[0][i]=a[i]+1;
   for (int i=1; i<LG; ++i) for (int j=1; j+(1<<i)-1<=n; ++j) st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
   int tl=sl, tc=sc;
   int ans=move(tl, tc, el, ec);
   for (int j=2; j<=n; ++j){
      val1[j]=calc(j, 1, {{j-1, a[j-1]+1}, {el, ec}})-j;
      val2[j]=calc(j, 1, {{j-1, a[j-1]+1}, {el, ec}})+j;
   }
   pf[1]=1e18;
   for (int j=2; j<=n; ++j){
      pf[j]=val1[j];
      if (j!=2) pf[j]=min(pf[j], pf[j-1]);
   }
   for (int j=n; j>=2; --j){
      sf[j]=val2[j];
      if (j!=n) sf[j]=min(sf[j], sf[j+1]);
   }
   sf[1]=sf[2];
   if (n==1) sf[1]=1e18;
   for (int i=1; i<=n; ++i){
      ans=min(ans, calc(sl, sc, {{i, -1}, {el, ec}}));
      if (i<n) ans=min(ans, calc(sl, sc, {{i, a[i]+1}, {i+1, 1}, {el, ec}}));
      // for (int j=2; j<=n; ++j){
      //    ans=min(ans, calc(sl, sc, {{i, 1}, {j, 1}, {j-1, a[j-1]+1}, {el, ec}}));
      //    if (i<n) ans=min(ans, calc(sl, sc, {{i, a[i]+1}, {i+1, 1}, {j, 1}, {j-1, a[j-1]+1}, {el, ec}}));
      // }
      ans=min(ans, calc(sl, sc, {{i, 1}})+min(pf[i]+i, sf[i]-i));
      if (i<n){
         ans=min(ans, calc(sl, sc, {{i, a[i]+1}, {i+1, 1}})+min(pf[i+1]+i+1, sf[i+1]-i-1));
      }
   }
   cout << ans << '\n';
   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