Submission #1180367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180367		LucaIlie	Text editor (CEOI24_editor)	C++20	45 / 100	955 ms	812172 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
struct edge {
    int u, v, c;
};

const int MAX_N = 1e6 + 10;
const int MAX_LOG_N = 21;
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];
int rmq[MAX_LOG_N + 1][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 p = log2( r - l + 1 );
    int minn = min( rmq[p][l], rmq[p][r - (1 << p) + 1] );

    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 getLeftLower( int l, int c ) {
    l--;
    while ( l >= 0 && len[l] > c )
        l--;
    return l;
}

int n;
int getRightLower( int l, int c ) {
    l++;
    while ( l < n && len[l] > c )
        l++;
    return (l == n ? -1 : l);
}

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

    int ls, cs, lf, cf;

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

    for ( int i = 0; i < n; i++ )
        rmq[0][i] = len[i];

    for ( int p = 1; (1 << p) <= n; p++ ) {
        for ( int i = 0; i <= n - (1 << p); i++ )
            rmq[p][i] = min( rmq[p - 1][i], rmq[p - 1][i + (1 << (p - 1))] );
    }

    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++ ) {
        addUndirectedEdge( start[i], finish[i], len[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 ( i > 0 && len[i] < len[i - 1] )
            addDirectedEdge( finish[i], finish[i - 1], 1 + len[i - 1] - len[i] );

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

        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 );
    }
    if ( minRange( ls, lf ) >= min( cs, cf ) )
        addDirectedEdge( source, sink, abs( lf - ls ) + abs( cf - cs ) );
    int ll = getLeftLower( ls, cs );
    if ( ll != -1 )
        addDirectedEdge( source, finish[ll], ls - ll );
    int rr = getRightLower( ls, cs );
    if ( rr != -1 )
        addDirectedEdge( source, finish[rr], rr - ls );

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

    return 0;
}

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