結果
| 問題 | No.1332 Range Nearest Query |
| ユーザー |
 kcvlex
|
| 提出日時 | 2021-01-08 23:54:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 315 ms / 2,500 ms |
| コード長 | 7,651 bytes |
| コンパイル時間 | 2,185 ms |
| コンパイル使用メモリ | 177,528 KB |
| 最終ジャッジ日時 | 2025-01-17 14:46:05 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 48 |
ソースコード
#include <limits>#include <initializer_list>#include <utility>#include <bitset>#include <tuple>#include <type_traits>#include <functional>#include <string>#include <array>#include <deque>#include <list>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <unordered_map>#include <unordered_set>#include <iterator>#include <algorithm>#include <complex>#include <random>#include <numeric>#include <iostream>#include <iomanip>#include <sstream>#include <regex>#include <cassert>#include <cstddef>#include <variant>#define endl codeforces#define ALL(v) std::begin(v), std::end(v)#define ALLR(v) std::rbegin(v), std::rend(v)using ll = std::int64_t;using ull = std::uint64_t;using pii = std::pair<int, int>;using tii = std::tuple<int, int, int>;using pll = std::pair<ll, ll>;using tll = std::tuple<ll, ll, ll>;using size_type = ssize_t;template <typename T> using vec = std::vector<T>;template <typename T> using vvec = vec<vec<T>>;template <typename T> const T& var_min(const T &t) { return t; }template <typename T> const T& var_max(const T &t) { return t; }template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }template <typename T, std::size_t Head, std::size_t... Tail>struct multi_dim_array { using type = std::array<typename multi_dim_array<T, Tail...>::type, Head>; };template <typename T, std::size_t Head>struct multi_dim_array<T, Head> { using type = std::array<T, Head>; };template <typename T, std::size_t... Args> using mdarray = typename multi_dim_array<T, Args...>::type;template <typename T, typename F, typename... Args>void fill_seq(T &t, F f, Args... args) {if constexpr (std::is_invocable<F, Args...>::value) {t = f(args...);} else {for (size_type i = 0; i < t.size(); i++) fill_seq(t[i], f, args..., i);}}template <typename T> vec<T> make_v(size_type sz) { return vec<T>(sz); }template <typename T, typename... Tail>auto make_v(size_type hs, Tail&&... ts) {auto v = std::move(make_v<T>(std::forward<Tail>(ts)...));return vec<decltype(v)>(hs, v);}namespace init__ {struct InitIO {InitIO() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << std::fixed << std::setprecision(30);}} init_io;}template <typename T>T ceil_pow2(T bound) {T ret = 1;while (ret < bound) ret *= 2;return ret;}template <typename T>T ceil_div(T a, T b) { return a / b + !!(a % b); }namespace utility {template <typename T>using validate_integer = typename std::enable_if<std::is_integral<T>::value, ll>::type;template <typename T>auto popcount(T n) -> validate_integer<T> {return __builtin_popcountll(n);}// 0 indexedtemplate <typename T>auto msb(T n) -> validate_integer<T> {return 64 - __builtin_clzll(n) - 1;}}namespace segtree {template <typename M>struct SegmentTree {vec<M> nodes;auto get_children_idx(size_type idx) {return std::make_pair(2 * idx, 2 * idx + 1);}void update_node(size_type i) {auto [ a, b ] = get_children_idx(i);nodes[i] = M::merge(nodes[a], nodes[b]);}public:template <typename F>SegmentTree(F f, size_type sz) {build(f, sz);}template <typename F>void build(F f, size_type sz) {nodes.resize(ceil_pow2(sz) * 2);auto offset = size();for (size_type i = 0; i < sz; i++) {nodes[i + offset] = f(i);}for (size_type i = offset - 1; 1 <= i; i--) {update_node(i);}}size_type size() const {return nodes.size() / 2;}const M& operator [](size_type i) const {return nodes[size() + i];}M get_query(ll ql, ll qr) const {M ret;size_type lnode = ql + size(), rnode = qr + size();while (lnode < rnode) {if (lnode & 1) {ret = M::merge(nodes[lnode], ret);lnode++;}if (rnode & 1) {rnode--;ret = M::merge(ret, nodes[rnode]);}lnode /= 2;rnode /= 2;}return ret;}void update_query(ll idx, M val) {idx += size();nodes[idx] = val;while (1 < idx) {ll pidx = idx / 2;update_node(pidx);idx = pidx;}}template <typename F>size_type lower_bound(F f) const {M sum;size_type l = 0, r = size(), idx = 0, bidx = 0;if (!f(nodes[0])) return -1;while (true) {if (r - l == 1) {if (!f(sum)) bidx++;break;}auto lidx = 2 * idx;auto ridx = lidx + 1;auto nsum = M::merge(sum, nodes[lidx]);size_type m = (l + r) / 2;if (f(nsum)) {r = m;idx = lidx;} else {l = m;idx = ridx;bidx = m;sum = std::move(nsum);}}return bidx;}};}#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")const ll inf = 1e10;int main() {ll n;std::cin >> n;vec<ll> xv(n);for (ll &e : xv) std::cin >> e;ll q;std::cin >> q;vec<tll> qv(q);for (auto &[ l, r, v ] : qv) {std::cin >> l >> r >> v;l--;}vec<ll> ans(q, inf);{struct M {ll v;M(ll arg = -inf) : v(arg) { }static M merge(M a, M b) { return M(std::max(a.v, b.v)); }};segtree::SegmentTree<M> seg([&](ll) { return M(); }, n);vec<std::pair<ll, ll>> pv;pv.reserve(n + q);for (ll i = 0; i < n; i++) pv.emplace_back(xv[i], -i - 1);for (ll i = 0; i < q; i++) pv.emplace_back(std::get<2>(qv[i]), i);std::sort(ALL(pv));for (auto [ x, i ] : pv) {if (i < 0) {const ll idx = -(i + 1);seg.update_query(idx, M(x));} else {auto [ l, r, x_ ] = qv[i];auto res = seg.get_query(l, r).v;chmin(ans[i], x - res);}}}{struct M {ll v;M(ll arg = inf) : v(arg) { }static M merge(M a, M b) { return M(std::min(a.v, b.v)); }};segtree::SegmentTree<M> seg([&](ll) { return M(); }, n);vec<std::pair<ll, ll>> pv;pv.reserve(n + q);for (ll i = 0; i < n; i++) pv.emplace_back(xv[i], i + 1);for (ll i = 0; i < q; i++) pv.emplace_back(std::get<2>(qv[i]), -i);std::sort(ALLR(pv));for (auto [ x, i ] : pv) {if (0 < i) {const ll idx = i - 1;seg.update_query(idx, M(x));} else {auto [ l, r, x_ ] = qv[-i];auto res = seg.get_query(l, r).v;chmin(ans[-i], res - x);}}}for (ll e : ans) std::cout << e << "\n";return 0;}