oj.uz

Submission #931249

# Submission time Handle Problem Language Result Execution time Memory
931249 2024-02-21T12:41:26 Z LucaIlie The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2984 ms 74768 KB 
#include <bits/stdc++.h>

#pragma GCC optimize(" unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)

using namespace std;

struct change {
    int time, val;
};

const int MAX_N = 1e5;
const int MAX_M = 2e5;
int n, m, d;
int h[MAX_N], a[MAX_M], b[MAX_M];
unordered_map<int, int> pos[MAX_N];
vector<int> trust[MAX_N];
vector<int> hx, hy;
vector<vector<vector<change>>> changes;
vector<change> emptyV;

void init( int N, int D, int H[] ) {
    n = N;
    d = D;
    for ( int i = 0; i < n; i++ )
        h[i] = H[i];
    changes.resize( n );
    emptyV.push_back( { -1, -1 } );
    for ( int i = 0; i < n; i++ ) {
        trust[i].push_back( i );
        changes[i].push_back( emptyV );
    }
}

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];
    }

    for ( int i = 0; i < m; i++ ) {
        if ( changes[a[i]].size() <= trust[a[i]].size() )
            changes[a[i]].push_back( emptyV );
        if ( changes[b[i]].size() <= trust[b[i]].size() )
            changes[b[i]].push_back( emptyV );

        if ( pos[a[i]][b[i]] == 0 ) {
            pos[a[i]][b[i]] = trust[a[i]].size();
            changes[a[i]][trust[a[i]].size()].push_back( { i, b[i] } );
            trust[a[i]].push_back( b[i] );

            pos[b[i]][a[i]] = trust[b[i]].size();
            changes[b[i]][trust[b[i]].size()].push_back( { i, a[i] } );
            trust[b[i]].push_back( a[i] );
        } else {
            int p, l;

            p = pos[a[i]][b[i]], l = trust[a[i]].size() - 1;
            swap( pos[a[i]][b[i]], pos[a[i]][trust[a[i]][l]] );
            swap( trust[a[i]][p], trust[a[i]][l] );
            changes[a[i]][p].push_back( { i, trust[a[i]][p] } );
            changes[a[i]][l].push_back( { i, -1 } );
            pos[a[i]][trust[a[i]][l]] = 0;
            trust[a[i]].pop_back();

            p = pos[b[i]][a[i]], l = trust[b[i]].size() - 1;
            swap( pos[b[i]][a[i]], pos[b[i]][trust[b[i]][l]] );
            swap( trust[b[i]][p], trust[b[i]][l] );
            changes[b[i]][p].push_back( { i, trust[b[i]][p] } );
            changes[b[i]][l].push_back( { i, -1 } );
            pos[b[i]][trust[b[i]][l]] = 0;
            trust[b[i]].pop_back();
        }
    }
}

int question( int x, int y, int t ) {
    hx.clear();
    for ( int i = 1; i < changes[x].size(); i++ ) {
        int l = 0, r = changes[x][i].size();
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;

            if ( changes[x][i][mid].time < t )
                l = mid;
            else
                r = mid;
        }
        if ( changes[x][i][l].val != -1 )
            hx.push_back( h[changes[x][i][l].val] );
    }
    hy.clear();
    for ( int i = 1; i < changes[y].size(); i++ ) {
        int l = 0, r = changes[y][i].size();
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;

            if ( changes[y][i][mid].time < t )
                l = mid;
            else
                r = mid;
        }
        if ( changes[y][i][l].val != -1 )
            hy.push_back( h[changes[y][i][l].val] );
    }

    sort( hx.begin(), hx.end() );
    sort( hy.begin(), hy.end() );

    int minDist = 1e9;
    int i = 0;
    for ( int j = 0; j < hy.size(); j++ ) {
        while ( i < hx.size() && hx[i] < hy[j] )
            i++;

        if ( i != hx.size() )
            minDist = min( minDist, hx[i] - hy[j] );
        if ( i > 0 )
            minDist = min( minDist, hy[j] - hx[i - 1] );
    }

    return minDist;
}

Compilation message

potion.cpp:4: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    4 | #pragma gcc optimize("Ofast")
      | 
potion.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization("Ofast")
      | 
potion.cpp:6: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    6 | #pragma optimize(Ofast)
      | 
potion.cpp:3:37: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize(" unroll-loops")
      |                                     ^
potion.cpp:24:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   24 | void init( int N, int D, int H[] ) {
      |                                  ^
potion.cpp:37:44: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   37 | void curseChanges( int M, int A[], int B[] ) {
      |                                            ^
potion.cpp:80:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   80 | int question( int x, int y, int t ) {
      |                                   ^
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:82:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<change> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for ( int i = 1; i < changes[x].size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~~~
potion.cpp:96:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<change> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for ( int i = 1; i < changes[y].size(); i++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~~~
potion.cpp:115:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for ( int j = 0; j < hy.size(); j++ ) {
      |                      ~~^~~~~~~~~~~
potion.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         while ( i < hx.size() && hx[i] < hy[j] )
      |                 ~~^~~~~~~~~~~
potion.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         if ( i != hx.size() )
      |              ~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Output is correct
2 Correct 3 ms 9048 KB Output is correct
3 Correct 4 ms 9048 KB Output is correct
4 Correct 28 ms 22032 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 74556 KB Output is correct
2 Correct 498 ms 74720 KB Output is correct
3 Correct 247 ms 31688 KB Output is correct
4 Correct 1651 ms 41328 KB Output is correct
5 Correct 609 ms 59376 KB Output is correct
6 Correct 2984 ms 58428 KB Output is correct
7 Correct 667 ms 58732 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 74768 KB Output is correct
2 Correct 1620 ms 45652 KB Output is correct
3 Correct 1069 ms 58600 KB Output is correct
4 Correct 1865 ms 58224 KB Output is correct
5 Correct 535 ms 74540 KB Output is correct
6 Correct 2112 ms 58356 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13000 KB Output is correct
2 Correct 70 ms 11220 KB Output is correct
3 Correct 117 ms 10840 KB Output is correct
4 Correct 717 ms 12884 KB Output is correct
5 Correct 708 ms 13140 KB Output is correct
6 Correct 69 ms 11368 KB Output is correct
7 Correct 613 ms 11096 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 3 ms 9048 KB Output is correct
3 Correct 3 ms 9048 KB Output is correct
4 Correct 4 ms 9048 KB Output is correct
5 Correct 28 ms 22032 KB Output is correct
6 Correct 480 ms 74556 KB Output is correct
7 Correct 498 ms 74720 KB Output is correct
8 Correct 247 ms 31688 KB Output is correct
9 Correct 1651 ms 41328 KB Output is correct
10 Correct 609 ms 59376 KB Output is correct
11 Correct 2984 ms 58428 KB Output is correct
12 Correct 667 ms 58732 KB Output is correct
13 Correct 515 ms 74768 KB Output is correct
14 Correct 1620 ms 45652 KB Output is correct
15 Correct 1069 ms 58600 KB Output is correct
16 Correct 1865 ms 58224 KB Output is correct
17 Correct 535 ms 74540 KB Output is correct
18 Correct 2112 ms 58356 KB Output is correct
19 Correct 40 ms 13000 KB Output is correct
20 Correct 70 ms 11220 KB Output is correct
21 Correct 117 ms 10840 KB Output is correct
22 Correct 717 ms 12884 KB Output is correct
23 Correct 708 ms 13140 KB Output is correct
24 Correct 69 ms 11368 KB Output is correct
25 Correct 613 ms 11096 KB Output is correct
26 Correct 845 ms 48556 KB Output is correct
27 Correct 1470 ms 58576 KB Output is correct
28 Correct 1671 ms 68736 KB Output is correct
29 Correct 1574 ms 41184 KB Output is correct
30 Correct 2827 ms 58520 KB Output is correct
31 Correct 2378 ms 45260 KB Output is correct
32 Correct 2608 ms 58268 KB Output is correct