#include <bits/stdc++.h>
using i64 = long long;
int n, d, u;
std::vector<int> h;
std::vector<int> a, b;
constexpr int BS = 1000;
int blocks;
std::vector<std::vector<std::unordered_set<int>>> trustListBlock;
constexpr int inf = 1000000000;
void init(int N, int D, int H[]) {
n = N;
d = D;
for (int i = 0; i < n; ++i) {
h.push_back(H[i]);
}
}
void curseChanges(int U, int A[], int B[]) {
u = U;
for (int i = 0; i < u; ++i) {
a.push_back(A[i]);
b.push_back(B[i]);
}
std::vector<std::unordered_set<int>> trustList(n);
for (int i = 0; i < u; ++i) {
if (i % BS == 0) {
trustListBlock.push_back(trustList);
}
if (trustList[a[i]].find(b[i]) == trustList[a[i]].end()) {
// insert
trustList[a[i]].insert(b[i]);
trustList[b[i]].insert(a[i]);
} else {
// erase
trustList[a[i]].erase(b[i]);
trustList[b[i]].erase(a[i]);
}
}
if (u % BS == 0) {
trustListBlock.push_back(trustList);
}
}
int question(int x, int y, int v) {
// check
const int l = v / BS * BS, r = v;
auto &trustList = trustListBlock[v / BS];
for (int i = l; i < r; ++i) {
if (trustList[a[i]].find(b[i]) == trustList[a[i]].end()) {
// insert
trustList[a[i]].insert(b[i]);
trustList[b[i]].insert(a[i]);
} else {
// erase
trustList[a[i]].erase(b[i]);
trustList[b[i]].erase(a[i]);
}
}
std::vector<std::pair<int, bool>> vals;
for (const int e : trustList[x]) {
vals.push_back({e, true});
}
for (const int e : trustList[y]) {
vals.push_back({e, false});
}
std::sort(vals.begin(), vals.end(), [&](const auto &a, const auto &b) {
return h[a.first] < h[b.first];
});
int answer = inf;
for (int i = 1; i < (int)vals.size(); ++i) {
if (vals[i - 1].second != vals[i].second) {
answer = std::min(answer, h[vals[i].first] - h[vals[i - 1].first]);
}
}
for (int i = r - 1; i >= l; --i) {
if (trustList[a[i]].find(b[i]) == trustList[a[i]].end()) {
// insert
trustList[a[i]].insert(b[i]);
trustList[b[i]].insert(a[i]);
} else {
// erase
trustList[a[i]].erase(b[i]);
trustList[b[i]].erase(a[i]);
}
}
return answer;
}
int main() {
int N, D, U, Q;
std::ios::sync_with_stdio(false); std::cin.tie(NULL);
std::cin >> N >> D >> U >> Q;
int *F = new int[N];
for (int i=0; i<N; i++)
std::cin >> F[i];
init(N, D, F);
int *A = new int[U], *B = new int[U];
for (int i=0; i<U; i++) {
std::cin >> A[i] >> B[i];
}
curseChanges(U, A, B);
bool correct = true;
for (int i=0; i<Q; i++) {
int X,Y,V,CorrectAnswer;
std::cin >> X >> Y >> V >> CorrectAnswer;
int YourAnswer = question(X,Y,V);
if (YourAnswer != CorrectAnswer) {
std::cout << "WA! Question: " << i
<< " (X=" << X << ", Y=" << Y << ", V=" << V << ") "
<< "Your answer: " << YourAnswer
<< " Correct Answer: " << CorrectAnswer << std::endl;
correct = false;
} else {
std::cerr << YourAnswer << " - OK" << std::endl;
}
}
if (correct) {
std::cout << "Correct." << std::endl;
} else std::cout << "Incorrect." << std::endl;
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccP8Sk9R.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccpyvcpS.o:potion.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
