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>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
int n, rad;
int *H0, *A0, *B0;
vi Perm, Inv;
vector<vi> Snapshot;
vector<vi> Mare;
vector<vi> S;
void init(int N, int D, int H[]) {
n = N;
H0 = H;
S.resize(n);
Inv.resize(n);
for(int i = 0; i < n; ++i)
Perm.push_back(i);
sort(Perm.begin(), Perm.end(), [&](auto a, auto b) {
return H[a] < H[b];
});
for(int i = 0; i < n; ++i)
Inv[Perm[i]] = i;
}
void curseChanges(int U, int A[], int B[]) {
rad = min(U, 500);
A0 = A;
B0 = B;
auto erase = [&](vi &V, int val) {
vi Re;
for(auto &it : V)
if(it != val) Re.push_back(it);
return Re;
};
vector<int> changed(n, 1);
for(int nr = 0; nr < U; ++nr) {
A[nr] = Inv[A[nr]];
B[nr] = Inv[B[nr]];
}
for(int nr = 0; nr < U; ++nr) {
if(nr % rad == 0) {
vi cur;
for(int i = 0; i < n; ++i) {
if(changed[i]) {
cur.push_back(Mare.size());
Mare.push_back(S[i]);
changed[i] = 0;
} else {
cur.push_back(Snapshot.back()[i]);
}
}
Snapshot.push_back(cur);
}
int a = A[nr], b = B[nr];
int ok = 0;
for(auto it : S[a])
if(it == b) ok = 1;
changed[a] = 1;
changed[b] = 1;
if(ok) {
S[a] = erase(S[a], b);
S[b] = erase(S[b], a);
} else {
S[b].push_back(a);
S[a].push_back(b);
}
}
}
const int INF = 1e9;
int question(int x, int y, int v) {
if(!v) {
return INF;
}
--v;
x = Inv[x];
y = Inv[y];
vi VSX = Mare[Snapshot[v / rad][x]];
vi VSY = Mare[Snapshot[v / rad][y]];
set<int> SX, SY;
for(auto it : VSX) SX.insert(it);
for(auto it : VSY) SY.insert(it);
for(int i = v / rad * rad; i <= v; ++i) {
int a = A0[i], b = B0[i];
if(b == x) swap(a, b);
if(a == x) {
if(SX.count(b)) SX.erase(b);
else SX.insert(b);
}
if(b == y) swap(a, b);
if(a == y) {
if(SY.count(b)) SY.erase(b);
else SY.insert(b);
}
}
vi VA, VB;
for(auto it : SX)
VA.push_back(H0[Perm[it]]);
for(auto it : SY)
VB.push_back(H0[Perm[it]]);
// for(auto it : VA) cerr << it << " ";
// cerr << "\n";
// for(auto it : VB) cerr << it << " ";
// cerr << "\n";
// cerr << "\n";
int p1 = 0, p2 = 0;
int re = INF;
while(p1 < VA.size() && p2 < VB.size()) {
re = min(re, abs(VB[p2] - VA[p1]));
if(VA[p1] < VB[p2]) ++p1;
else ++p2;
}
return re;
}
Compilation message (stderr)
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:122:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | while(p1 < VA.size() && p2 < VB.size()) {
| ~~~^~~~~~~~~~~
potion.cpp:122:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | while(p1 < VA.size() && p2 < VB.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... |