| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 410180 | KoD | The Potion of Great Power (CEOI20_potion) | C++17 | 0 ms | 0 KiB |
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 i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
class rep {
struct Iter {
usize itr;
constexpr Iter(const usize pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
constexpr usize operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
template <class T> using Vec = std::vector<T>;
void main_() {
usize N, D, U, Q;
std::cin >> N >> D >> U >> Q;
Vec<i32> H(N);
for (auto& x : H) {
std::cin >> x;
}
Vec<Vec<usize>> snapshot(N);
Vec<Vec<std::multiset<i32>>> set(N);
Vec<Vec<Vec<std::tuple<usize, i32, bool>>>> log(N);
for (const auto i : rep(0, N)) {
snapshot[i].push_back(0);
set[i].emplace_back();
log[i].emplace_back();
}
{
Vec<std::multiset<i32>> cur(N);
std::map<std::pair<usize, usize>, bool> exist;
for (const auto i : rep(0, U)) {
usize x, y;
std::cin >> x >> y;
if (x > y) std::swap(x, y);
if (exist[{x, y}] ^= 1) {
cur[x].insert(H[y]);
log[x].back().emplace_back(i, H[y], true);
cur[y].insert(H[x]);
log[y].back().emplace_back(i, H[x], true);
} else {
cur[x].erase(cur[x].find(H[y]));
log[x].back().emplace_back(i, H[y], false);
cur[y].erase(cur[y].find(H[x]));
log[y].back().emplace_back(i, H[x], false);
}
if (log[x].back().size() == 50) {
snapshot[x].push_back(i + 1);
set[x].push_back(cur[x]);
log[x].push_back({});
}
if (log[y].back().size() == 50) {
snapshot[y].push_back(i + 1);
set[y].push_back(cur[y]);
log[y].push_back({});
}
}
}
while (Q--) {
usize x, y, u;
std::cin >> x >> y >> u;
const usize s_x = std::upper_bound(snapshot[x].begin(), snapshot[x].end(), u) - snapshot[x].begin() - 1;
std::multiset<i32> set_x = set[x][s_x];
for (const auto [i, v, f] : log[x][s_x]) {
if (u <= i) break;
if (f)
set_x.insert(v);
else
set_x.erase(set_x.find(v));
}
const usize s_y = std::upper_bound(snapshot[y].begin(), snapshot[y].end(), u) - snapshot[y].begin() - 1;
std::multiset<i32> set_y = set[y][s_y];
for (const auto [i, v, f] : log[y][s_y]) {
if (u <= i) break;
if (f)
set_y.insert(v);
else
set_y.erase(set_y.find(v));
}
i32 ans = 1000000000;
auto itr_x = set_x.begin();
auto itr_y = set_y.begin();
while (itr_x != set_x.end() and itr_y != set_y.end()) {
ans = std::min(ans, std::abs(*itr_x - *itr_y));
if (*itr_x <= *itr_y) {
++itr_x;
} else {
++itr_y;
}
}
std::cout << ans << std::endl;
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
main_();
return 0;
}