#include <bits/stdc++.h>
using namespace std;
int n, d, u, q;
vector<int> h, a, b;
vector< vector<int> > updates;
vector< vector< vector<int> > > seg;
void update(int idx, int l, int r, int i, int j, int a, int b) {
if (l > j || r < i) {
return;
}
if (l >= i && j >= r) {
seg[a][idx].push_back(h[b]);
return;
}
update(2 * idx, l, (l + r) / 2, i, j, a, b);
update(2 * idx + 1, (l + r) / 2 + 1, r, i, j, a, b);
}
vector<int> neighbors(int a, int v) {
auto it = upper_bound(updates[a].begin(), updates[a].end(), v);
if (it == updates[a].begin()) {
return {};
}
v = it - updates[a].begin() - 1;
int l = 0, r = (int) updates[a].size() - 1, idx = 1;
vector<int> ans;
while (1) {
for (auto& x : seg[a][idx]) {
ans.push_back(x);
}
if (l == r) {
break;
}
if (v <= (l + r) / 2) {
idx = 2 * idx;
r = (l + r) / 2;
} else {
idx = 2 * idx + 1;
l = (l + r) / 2 + 1;
}
}
return move(ans);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> d >> u >> q;
h.resize(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
a.resize(u);
b.resize(u);
updates.assign(n, {0});
for (int i = 0; i < u; i++) {
cin >> a[i] >> b[i];
updates[a[i]].push_back(i + 1);
updates[b[i]].push_back(i + 1);
}
seg.resize(n);
for (int i = 0; i < n; i++) {
seg[i].resize(4 * (int) updates[i].size());
}
auto add = [&](int a, int b, int st, int en) {
int i = lower_bound(updates[a].begin(), updates[a].end(), st) - updates[a].begin();
int j = upper_bound(updates[a].begin(), updates[a].end(), en) - updates[a].begin() - 1;
update(1, 0, (int) updates[a].size() - 1, i, j, a, b);
};
map< pair<int, int>, int> mp;
for (int i = 0; i < u; i++) {
if (a[i] > b[i]) {
swap(a[i], b[i]);
}
if (mp.count({a[i], b[i]})) {
add(a[i], b[i], mp[{a[i], b[i]}], i);
add(b[i], a[i], mp[{a[i], b[i]}], i);
mp.erase({a[i], b[i]});
} else {
mp[{a[i], b[i]}] = i + 1;
}
}
for (auto& p : mp) {
add(p.first.first, p.first.second, p.second, u);
add(p.first.second, p.first.first, p.second, u);
}
while (q--) {
int x, y, v;//, ac;
cin >> x >> y >> v;// >> ac;
vector<int> v_x = neighbors(x, v);
vector<int> v_y = neighbors(y, v);
sort(v_x.begin(), v_x.end());
sort(v_y.begin(), v_y.end());
int i = 0, j = 0;
int ans = (int) 1e9;
while (i < (int) v_x.size() && j < (int) v_y.size()) {
ans = min(ans, abs(v_x[i] - v_y[j]));
if (v_x[i] <= v_y[j]) {
i++;
} else {
j++;
}
}
cout << ans << endl;
}
return 0;
}
Compilation message
potion.cpp: In function 'std::vector<int> neighbors(int, int)':
potion.cpp:44:14: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
44 | return move(ans);
| ~~~~^~~~~
potion.cpp:44:14: note: remove 'std::move' call
/usr/bin/ld: /tmp/ccldBHqy.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccB4KGYw.o:potion.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccldBHqy.o: in function `main':
grader.cpp:(.text.startup+0xec): undefined reference to `init(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x184): undefined reference to `curseChanges(int, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x1d9): undefined reference to `question(int, int, int)'
collect2: error: ld returned 1 exit status
