Submission #931159

#	Time	Username	Problem	Language	Result	Execution time	Memory
931159		LucaIlie	The Potion of Great Power (CEOI20_potion)	C++17	17 / 100	3094 ms	5056 KiB

potion

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int MAX_M = 2e5;
int n, m, d;
int h[MAX_N], a[MAX_M], b[MAX_M];

void init( int N, int D, int H[] ) {
    n = N;
    d = D;
    for ( int i = 0; i < n; i++ )
        h[i] = H[i];
}

void curseChanges( int M, int A[], int B[] ) {
    m = M;
    for ( int i = 0; i < M; i++ ) {
        a[i] = A[i];
        b[i] = B[i];
    }
}

set<int> hy, sx, sy;
int question( int x, int y, int t ) {
    sx.clear();
    sy.clear();
    for ( int i = 0; i < t; i++ ) {
        if ( b[i] == x )
            swap( a[i], b[i] );
        if ( a[i] == y )
            swap( a[i], b[i] );


        if ( a[i] == x ) {
            if ( sx.find( b[i] ) == sx.end() )
            sx.insert( b[i] );
        else
            sx.erase( b[i] );
        }

        if ( b[i] == y ) {
            if ( sy.find( a[i] ) == sy.end() )
                sy.insert( a[i] );
            else
                sy.erase( a[i] );
        }
    }

    hy.clear();
    for ( int i: sy )
        hy.insert( h[i] );

    int minDist = 1e9;
    for ( int i: sx ) {
        int hx = h[i];
        auto p = hy.upper_bound( hx );
        if ( p != hy.end() )
            minDist = min( minDist, *p - hx );
        if ( p != hy.begin() ) {
            p--;
            minDist = min( minDist, hx - *p );
        }
    }
    
    return minDist;
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30