제출 #1180324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180324		LucaIlie	Text editor (CEOI24_editor)	C++20	0 / 100	25 ms	47684 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, c;
};

const int MAX_N = 1e6;
const long long INF = 1e18;
long long dist[MAX_N];
int len[MAX_N], leftLower[MAX_N], rightLower[MAX_N], start[MAX_N], finish[MAX_N];
bool vis[2 * MAX_N + 2];
vector<edge> edges;
vector<int> adj[2 * MAX_N + 2];

void addDirectedEdge( int u, int v, int c ) {
    //printf( "%d %d %d\n", u, v, c );
    adj[u].push_back( edges.size() );
    adj[v].push_back( edges.size() );
    edges.push_back( { u, v, c } );
}

void addUndirectedEdge( int u, int v, int c ) {
    addDirectedEdge( u, v, c );
    addDirectedEdge( v, u, c );
}

int minRange( int l, int r ) {
    if ( l > r )
        swap( l, r );

    int minn = 1e9;
    for ( int i = l; i <= r; i++ )
        minn = min( minn, len[i] );

    return minn;
}

long long dijkstra( int n, int source, int sink ) {
    for ( int i = 0; i < n; i++ )
        dist[i] = INF, vis[i] = false;;

    priority_queue<pair<long long, int>> pq;
    dist[source] = 0;
    pq.push( { -dist[source], source } );
    while ( !pq.empty() ) {
        int u = pq.top().second;
        pq.pop();

        if ( vis[u] )
            continue;
        vis[u] = true;

        for ( int e: adj[u] ) {
            int v = edges[e].v, c = edges[e].c;
            if ( dist[u] + c < dist[v] ) {
                dist[v] = dist[u] + c;
                pq.push( { -dist[v], v } );
            }
        }
    }

    //for ( int i = 0; i < n; i++ ) {
    //    printf( "%d %d\n", i, dist[i] );
    //}

    return dist[sink];
}

int main() {
    cin.tie( nullptr );

    int n, ls, cs, lf, cf;

    cin >> n >> ls >> cs >> lf >> cf;
    ls--;
    cs--;
    lf--;
    cf--;
    for ( int i = 0; i < n; i++ )
        cin >> len[i];

    vector<int> st;
    for ( int i = 0; i < n; i++ ) {
        while ( !st.empty() && len[i] <= len[st.back()] )
            st.pop_back();
        if ( !st.empty() )
            leftLower[i] = st.back();
        else
            leftLower[i] = -1;
        st.push_back( i );
    }
    for ( int i = n - 1; i >= 0; i-- ) {
        while ( !st.empty() && len[i] <= len[st.back()] )
            st.pop_back();
        if ( !st.empty() )
            rightLower[i] = st.back();
        else
            rightLower[i] = -1;
        st.push_back( i );
    }

    for ( int i = 0; i < n; i++ )
        start[i] = i + 1, finish[i] = i + 1 + n;

    int source = 0, sink = 2 * n + 1;
    for ( int i = 0; i < n; i++ ) {
        if ( i > 0 )
            addUndirectedEdge( start[i], finish[i - 1], 1 );

        if ( i > 0 )
            addUndirectedEdge( start[i], start[i - 1], 1 );

        if ( i > 0 && len[i] >= len[i - 1] )
            addDirectedEdge( finish[i], finish[i - 1], 1 );

        if ( i < n - 1 && len[i] >= len[i + 1] )
            addDirectedEdge( finish[i], finish[i + 1], 1 );

        if ( leftLower[i] != -1 )
            addDirectedEdge( finish[i], finish[leftLower[i]], i - leftLower[i] );
        
        if ( rightLower[i] != -1 )
            addDirectedEdge( finish[i], finish[rightLower[i]], rightLower[i] - i );

        if ( minRange( ls, i ) <= min( len[i], cs ) )
            addDirectedEdge( source, finish[i], abs( ls - i ) + abs( cs - len[i] ) );
        addDirectedEdge( source, start[i], abs( ls - i ) + cs );

        if ( minRange( lf, i ) <= min( len[i], cf ) )
            addDirectedEdge( finish[i], sink, abs( lf - i ) + abs( cf - len[i] ) );
        addDirectedEdge( start[i], sink, abs( lf - i ) + cf );
    }

    long long ans = dijkstra( 2 * n + 2, source, sink );
    cout << ans << "\n";

    return 0;
}

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