oj.uz

Submission #931159

# Submission time Handle Problem Language Result Execution time Memory
931159 2024-02-21T10:20:54 Z LucaIlie The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 5056 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 10 ms 1616 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 4364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 5056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 700 KB Output is correct
2 Correct 641 ms 856 KB Output is correct
3 Correct 2858 ms 600 KB Output is correct
4 Execution timed out 3094 ms 600 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 10 ms 1616 KB Output is correct
6 Execution timed out 3042 ms 4364 KB Time limit exceeded
7 Halted 0 ms 0 KB -