This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
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 (stderr)
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:77:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<change> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for ( int i = 1; i < changes[x].size(); i++ ) {
| ~~^~~~~~~~~~~~~~~~~~~
potion.cpp:91:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<change> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for ( int i = 1; i < changes[y].size(); i++ ) {
| ~~^~~~~~~~~~~~~~~~~~~
potion.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for ( int j = 0; j < hy.size(); j++ ) {
| ~~^~~~~~~~~~~
potion.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | while ( i < hx.size() && hx[i] < hy[j] )
| ~~^~~~~~~~~~~
potion.cpp:114:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | if ( i != hx.size() )
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |