#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(x) (int) x.size()
const int N = 100'005, D = 505;
vector<array<int, 2>> gud[N][D];
vector<int> rem[N];
set<array<int, 2>> adj[N];
int a[N], n, m;
void init(int _n, int d, int h[]) {
n = _n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 500; j++) {
rem[i].push_back(j);
}
}
for (int i = 0; i < n; i++) {
a[i] = h[i];
}
}
void upd(int i, int j, int v, int t) {
gud[i][j].push_back({v, t});
}
void curseChanges(int _m, int A[], int B[]) {
m = _m;
for (int i = 0; i < m; i++) {
int u = A[i], v = B[i];
auto it = adj[u].lower_bound({v, 0});
if (it != adj[u].end() && (*it)[0] == v) {
int x = (*it)[1];
upd(u, x, -1, i + 1);
rem[u].push_back(x);
adj[u].erase({v, x});
it = adj[v].lower_bound({u, 0});
x = (*it)[1];
upd(v, x, -1, i + 1);
rem[v].push_back(x);
adj[v].erase({u, x});
} else {
int x = rem[u].back();
upd(u, x, a[v], i + 1);
rem[u].pop_back();
adj[u].insert({v, x});
x = rem[v].back();
upd(v, x, a[u], i + 1);
rem[v].pop_back();
adj[v].insert({u, x});
}
}
}
int question(int x, int y, int v) {
vector<int> v1, v2;
for (int j = 0; j < 500; j++) {
int l = 0, r = sz(gud[x][j]) - 1;
while (l <= r) {
int md = ((l + r) >> 1);
if (gud[x][j][md][1] <= v) {
l = md + 1;
} else {
r = md - 1;
}
}
if (r >= 0 && gud[x][j][r][0] != -1) {
v1.push_back(gud[x][j][r][0]);
}
l = 0, r = sz(gud[y][j]) - 1;
while (l <= r) {
int md = ((l + r) >> 1);
if (gud[y][j][md][1] <= v) {
l = md + 1;
} else {
r = md - 1;
}
}
if (r >= 0 && gud[y][j][r][0] != -1) {
v2.push_back(gud[y][j][r][0]);
}
}
int ans = 1e9;
if (v1.empty() || v2.empty()) {
return ans;
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
int ptr = 0;
for (int i = 0; i < sz(v1); i++) {
while (ptr + 1 < sz(v2) && v2[ptr + 1] <= v1[i]) {
ptr++;
}
ans = min(ans, abs(v1[i] - v2[ptr]));
if (ptr + 1 < sz(v2)) {
ans = min(ans, abs(v1[i] - v2[ptr + 1]));
}
}
return ans;
}
#ifdef MINA
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int _N = 6, _D = 5, U = 11;
int H[] = {2, 42, 1000, 54, 68, 234};
int A[] = {0, 2, 3, 3, 3, 1, 5, 0, 3, 1, 3};
int B[] = {1, 0, 4, 5, 5, 3, 3, 5, 0, 3, 5};
init(_N, _D, H);
curseChanges(U, A, B);
cout << question(0, 3, 4) << '\n';
cout << question(3, 0, 8) << '\n';
cout << question(0, 5, 5) << '\n';
cout << question(3, 0, 11) << '\n';
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
126 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
70 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
69 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
72 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
126 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
