Submission #1227239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227239		Malix	Text editor (CEOI24_editor)	C++20	5 / 100	133 ms	9516 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<ll,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;cin>>n;
    pi P,Q;
    cin>>P.F>>P.S>>Q.F>>Q.S;
    P.F--;P.S--;Q.F--;Q.S--;
    vi b(n);
    REP(i,0,n)cin>>b[i];
    map<pi,vector<ti>> a;
    map<pi,ll> dist;
    int mn=min(P.S,Q.S),mx=max(P.S,Q.S);
    ll dif=(ll)mx-(ll)mn;
    REP(i,0,n){
        if(i!=0){
            a[{i,0}].PB({1,i-1,b[i-1]});
            if(b[i-1]<b[i]){
                if(mx>b[i-1])a[{i,mx}].PB({1,i-1,b[i-1]});
                if(mn>b[i-1])a[{i,mn}].PB({1,i-1,b[i-1]});
                a[{i,b[i]}].PB({1,i-1,b[i-1]});
                a[{i,b[i]}].PB({b[i]-b[i-1],i,b[i-1]});
                a[{i,b[i-1]}].PB({b[i]-b[i-1],i,b[i]});
                if(b[i-1]>mx){
                    a[{i,b[i-1]}].PB({b[i-1]-mx,i,mx});
                    a[{i,mx}].PB({b[i-1]-mx,i,b[i-1]});
                }
                else if(b[i-1]>mn){
                    a[{i,b[i-1]}].PB({abs(b[i-1]-mn),i,mn});
                    a[{i,mn}].PB({abs(b[i-1]-mn),i,b[i-1]});
                    if(b[i]>mn){
                        a[{i,b[i-1]}].PB({abs(b[i-1]-mx),i,mx});
                        a[{i,mx}].PB({abs(b[i-1]-mx),i,b[i-1]});
                    }
                }
                else{
                    a[{i,b[i-1]}].PB({b[i-1],i,0});
                    a[{i,0}].PB({b[i-1],i,b[i-1]});
                    if(b[i]>mn){
                        a[{i,b[i-1]}].PB({abs(b[i-1]-mn),i,mn});
                        a[{i,mn}].PB({abs(b[i-1]-mn),i,b[i-1]});
                    }
                }
            }
            else a[{i,b[i]}].PB({1,i-1,b[i]});
        }
        if(i!=n-1){
            if(mx>b[i+1])a[{i,mx}].PB({1,i+1,b[i+1]});
            if(mn>b[i+1])a[{i,mn}].PB({1,i+1,b[i+1]});
            a[{i,0}].PB({1,i+1,0});
            if(b[i+1]<b[i]){
                a[{i,b[i]}].PB({1,i+1,b[i+1]});
                a[{i,b[i]}].PB({b[i]-b[i+1],i,b[i+1]});
                a[{i,b[i+1]}].PB({b[i]-b[i+1],i,b[i]});
                if(b[i+1]>mx){
                    a[{i,b[i+1]}].PB({b[i+1]-mx,i,mx});
                    a[{i,mx}].PB({b[i+1]-mx,i,b[i+1]});
                }
                else if(b[i+1]>mn){
                    a[{i,b[i+1]}].PB({abs(b[i+1]-mn),i,mn});
                    a[{i,mn}].PB({abs(b[i+1]-mn),i,b[i+1]});
                    if(b[i]>mn){
                        a[{i,b[i+1]}].PB({abs(b[i+1]-mx),i,mx});
                        a[{i,mx}].PB({abs(b[i+1]-mx),i,b[i+1]});
                    }
                }
                else{
                    a[{i,b[i+1]}].PB({b[i+1],i,0});
                    a[{i,0}].PB({b[i+1],i,b[i+1]});
                    if(b[i]>mn){
                        a[{i,b[i+1]}].PB({abs(b[i+1]-mn),i,mn});
                        a[{i,mn}].PB({abs(b[i+1]-mn),i,b[i+1]});
                    }
                }
            }
            else a[{i,b[i]}].PB({1,i+1,b[i]});
        }
        a[{i,0}].PB({b[i],i,b[i]});
        a[{i,b[i]}].PB({b[i],i,0});
        if(b[i]>mx){
            a[{i,0}].PB({mn,i,mn});
            a[{i,mn}].PB({mn,i,0});
            a[{i,mx}].PB({dif,i,mn});
            a[{i,mn}].PB({dif,i,mx});
            a[{i,mx}].PB({b[i]-mx,i,b[i]});
            a[{i,b[i]}].PB({b[i]-mx,i,mx});
        }
        else if(b[i]>mn){
            a[{i,0}].PB({mn,i,mn});
            a[{i,mn}].PB({mn,i,0});
            a[{i,mn}].PB({b[i]-mn,i,b[i]});
            a[{i,b[i]}].PB({b[i]-mn,i,mn});
        }
    }
    for(auto [u,v]:a)dist[u]=INF;
    dist[P]=0;
    priority_queue<ti,vector<ti>,greater<ti>> pq;
    pq.push({0,P.F,P.S});
    while(!pq.empty()){
        auto [z,x,y]=pq.top();
        pq.pop();
        if(dist[{x,y}]<z)continue;
        for(auto u:a[{x,y}]){
            auto [p,q,r]=u;
            if(p==0)continue;
            if(dist[{q,r}]<dist[{x,y}]+p)continue;
            dist[{q,r}]=dist[{x,y}]+p;
            pq.push({dist[{q,r}],q,r});
        }
    }
    cout<<dist[Q];
}

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