Submission #1073655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073655		_8_8_	Text editor (CEOI24_editor)	C++17	16 / 100	1116 ms	66252 KiB

Main

#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 12, MOD = (int)1e9 + 7;

int n,l[N],d[N],t[N * 4],val[N];
void build(int v = 1,int tl = 1,int tr = n) {
    if(tl == tr) {
        t[v] = l[tl];
    } else {
        int tm = (tl + tr) >> 1;
        build(v + v,tl,tm);
        build(v + v + 1,tm + 1,tr);
        t[v] = min(t[v + v],t[v + v + 1]);
    }
}
const int inf = 1e9 + 2;
int get(int l,int r,int v = 1,int tl = 1,int tr = n) {
    if(l > r || tl > r || l > tr) return inf;
    if(tl >= l && tr <= r) {
        return t[v];
    }   
    int tm = (tl + tr) >> 1;
    return min(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
}
int res = inf, x, y;
void calc() {
    d[x] = y - 1;
    for(int i = x + 1;i <= n;i++) {
        int t = min(y,get(x,i));
        d[i] = i - x + t - 1;
        t = min(y,get(x,i - 1));
        d[i] = min(d[i],(i - 1) - x + l[i - 1] - t + 1);
    }
    for(int i = x - 1;i >= 1;i--) {
        int t = min(y,get(i,x));
        d[i] = x - i + t - 1;
    }
    set<pair<int,int>> st;
    for(int i = 1;i <= n;i++) {
        st.insert({d[i],i});
    }
    while(!st.empty()) {
        auto [z,v] = (*st.begin());
        st.erase(st.begin());
        auto upd = [&](int x) {
            if(x < 1 || x > n) return;
            if(d[x] > d[v] + 1) {
                st.erase({d[x],x});
                d[x] = d[v] + 1;
                st.insert({d[x],x});
            }
        };
        upd(v - 1);
        upd(v + 1);
    }
    // for(int i = 1;i <= n;i++) {
    //     cout << i << ' ' << d[i] << '\n';
    // }
}
void test() {
    int x1, y1;
    cin >> n >> x >> y >> x1 >> y1;
    for(int i = 1; i <= n; i++) {
        cin >> l[i];
        l[i]++;
    }
    build();
    // dont visit col 1
    auto get1 = [&](int l,int r) {
        if(r < l) swap(l,r);
        return get(l,r);
    };
    for(int i = 1;i <= min(x,x1);i++) {
        int v = min({y,get1(i,x),get1(i,x1)});
        res = min(res,abs(x - i) + abs(x1 - i) + abs(y1 - v));
    }
    for(int i = max(x,x1);i <= n;i++) {
        int v = min({y,get1(i,x),get1(i,x1)});
        res = min(res,abs(x - i) + abs(x1 - i) + abs(y1 - v));
    }
    //visit col 1
    calc();
    res = min(res,d[x1] + y1 - 1);
    int mn = l[x1],mn1 = abs(l[x1] - y1) - x1;
    for(int i = x1 + 1;i <= n;i++) {
        int t = abs(y1 - get(x1,i - 1)) + (i - 1 - x1) + 1 + d[i];
        res = min(res,t);
        if(l[i] > mn) continue;
        res = min(res,d[i] + i + mn1);
        mn = l[i];
        mn1 = min(mn1,abs(l[i] - y1) + x1);
    }
    for(int i = x1; i > 1; i--) {
        int t = abs(y1 - get(i - 1,x1)) + (x1 - (i - 1)) + 1 + d[i];
        res = min(res,t);
    }
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

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