Submission #1140851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140851		adiyer	Text editor (CEOI24_editor)	C++20	5 / 100	4089 ms	617240 KiB

Main

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>

#define all(x) x.begin(), x.end()
#define F first
#define S second

using namespace std;

typedef long long ll;

const int N = 4e6 + 11;
const int mod = 1e9 + 7;
const ll inf = 1e12 + 11;

ll n, sx, sy, fx, fy, sz;
ll l[N], dis[N], a[N], b[N], c[N], d[N];

vector < pair < ll, ll > > g[N];

map < pair < ll, ll >, ll > id;

void dijkstra(ll s){
  set < pair < ll, ll > > q;
  for(ll i = 0; i <= sz; i++) dis[i] = inf;
  dis[s] = 0, q.insert({dis[s], s});
  while(!q.empty()){
    ll v = (q.begin() -> S);
    q.erase(q.begin());
    for(auto [u, w] : g[v])
      if(dis[v] + w < dis[u])
        q.erase({dis[u], u}), dis[u] = dis[v] + w, q.insert({dis[u], u});
  }
}
signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> sx >> sy >> fx >> fy;
  for(ll i = 1; i <= n; i++) cin >> l[i], l[i]++;
  for(ll i = 1; i <= n; i++){
    a[i] = 1, b[i] = min(l[i], sy), c[i] = min(l[i], fy), d[i] = l[i];
    if(b[i] > c[i]) swap(b[i], c[i]);
    if(!id[{i, a[i]}]) id[{i, a[i]}] = ++sz;
    if(!id[{i, b[i]}]) id[{i, b[i]}] = ++sz;
    if(!id[{i, c[i]}]) id[{i, c[i]}] = ++sz;
    if(!id[{i, d[i]}]) id[{i, d[i]}] = ++sz;
    ll f1 = id[{i, a[i]}], f2 = id[{i, b[i]}], f3 = id[{i, c[i]}], f4 = id[{i, d[i]}];
    if(f1 != f2) g[f1].push_back({f2, b[i] - a[i]}), g[f2].push_back({f1, b[i] - a[i]});
    if(f2 != f3) g[f2].push_back({f3, c[i] - b[i]}), g[f3].push_back({f2, c[i] - b[i]});
    if(f3 != f4) g[f3].push_back({f4, d[i] - c[i]}), g[f4].push_back({f3, d[i] - c[i]});
    if(i > 1){
      if(f1 != id[{i - 1, l[i - 1]}]){ 
        g[f1].push_back({id[{i - 1, l[i - 1]}], 1});
        g[id[{i - 1, l[i - 1]}]].push_back({f1, 1});
      }
    }
  }
  for(ll i = 2; i <= n; i++){
    g[id[{i - 1, a[i - 1]}]].push_back({id[{i, a[i]}], 1});
    g[id[{i, a[i]}]].push_back({id[{i - 1, a[i - 1]}], 1});
    g[id[{i, d[i]}]].push_back({id[{i - 1, min(d[i], d[i - 1])}], 1});
    g[id[{i - 1, d[i - 1]}]].push_back({id[{i, min(d[i], d[i - 1])}], 1});
    g[id[{i, c[i]}]].push_back({id[{i - 1, min(c[i], c[i - 1])}], 1});
    g[id[{i - 1, c[i - 1]}]].push_back({id[{i, min(c[i], c[i - 1])}], 1});
    g[id[{i, b[i]}]].push_back({id[{i - 1, min(b[i], b[i - 1])}], 1});
    g[id[{i - 1, b[i - 1]}]].push_back({id[{i, min(b[i], b[i - 1])}], 1});
  }
  // for(ll i = 1; i <= n; i++){
  //   cout << "text: ";
  //   for(ll j = 1; j <= l[i]; j++){
  //     cout << id[{i, j}] << ' ';
  //   }
  //   cout << '\n';
  // }
  // for(ll i = 1; i <= sz; i++){
  //   for(auto [j, w] : g[i]){
  //     cout << i << ' ' << j << ' ' << w << '\n';
  //   }
  // }
  dijkstra(id[{sx, sy}]);
  cout << dis[id[{fx, fy}]];
}

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