結果
| 問題 | No.1332 Range Nearest Query |
| コンテスト | |
| ユーザー |
 ooaiu
|
| 提出日時 | 2026-07-27 21:53:56 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 277 ms / 2,500 ms |
| + 953µs | |
| コード長 | 10,324 bytes |
| 記録 | |
| コンパイル時間 | 2,914 ms |
| コンパイル使用メモリ | 353,836 KB |
| 実行使用メモリ | 11,136 KB |
| 最終ジャッジ日時 | 2026-07-27 21:54:20 |
| 合計ジャッジ時間 | 17,021 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 48 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
template <class F> class y_combinator {
F f;
public:
y_combinator(F&& f) : f(std::forward<F>(f)) {}
template <class... Args> auto operator()(Args&&... args) const { return f(*this, std::forward<Args>(args)...); }
};
constexpr int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vc<T>>;
template <class T, class U = std::less<T>> using prique = priority_queue<T, vector<T>, U>;
#define overload(a, b, c, d, e, ...) e
#define len(x) (ll)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep1(n) for (ll _ = 0; _ < ll(n); _++)
#define rep2(i, n) for (ll i = 0; i < ll(n); i++)
#define rep3(i, a, b) for (ll i = ll(a); i < ll(b); i++)
#define rep4(i, a, b, c) for (ll i = ll(a); i < ll(b); i += ll(c))
#define rep(...) overload(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(i, n) for (ll i = ll(n) - 1; i >= 0; i--)
template <class T> void dedup(vector<T>& a) { sort(all(a)), a.erase(unique(all(a)), a.end()); }
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
namespace cppio {
template <typename T> struct is_tuple_like : false_type {};
template <typename... Ts> struct is_tuple_like<tuple<Ts...>> : true_type {};
template <typename T, typename U> struct is_tuple_like<pair<T, U>> : true_type {};
template <typename T, typename = void> struct is_container : false_type {};
template <typename T> struct is_container<T, void_t<decltype(begin(declval<T&>()))>> : bool_constant<!is_same_v<decay_t<T>, string> && !is_same_v<decay_t<T>, char*> && !is_same_v<decay_t<T>, const char*> && !is_array_v<remove_reference_t<T>>> {};
template <typename T> void _in(T& x) {
if constexpr (is_tuple_like<T>::value) apply([](auto&... elems) { (_in(elems), ...); }, x);
else if constexpr (is_container<T>::value) {
for (auto& e : x) _in(e);
} else cin >> x;
}
template <typename... Ts> void _in_all(Ts&... args) { (_in(args), ...); }
template <typename T> void _out(const T& x) {
bool first = true;
if constexpr (is_tuple_like<T>::value) {
apply([&](const auto&... elems) { ((cout << (first ? "" : " "), _out(elems), first = false), ...); }, x);
} else if constexpr (is_container<T>::value) {
for (const auto& e : x) {
if (!first) cout << ' ';
_out(e), first = false;
}
} else cout << x;
}
template <typename... Ts> void _print(const Ts&... args) {
bool first = true;
((cout << (first ? "" : " "), _out(args), first = false), ...);
}
template <typename... Ts> void _out_all(const Ts&... args) { _print(args...), cout << '\n'; }
template <typename... Ts> void _out_no_el(const Ts&... args) { _print(args...); }
} // namespace cppio
#define IN(...) cppio::_in_all(__VA_ARGS__)
#define OUT(...) cppio::_out_all(__VA_ARGS__)
#define out(...) cppio::_out_no_el(__VA_ARGS__)
#define INT(...) int __VA_ARGS__; IN(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; IN(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; IN(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; IN(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); IN(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); IN(name)
#define RETURN(...) do { __VA_ARGS__; return; } while (0)
bool Yes(bool b = true) { OUT(b ? "Yes" : "No"); return b; }
bool No(bool b = true) { Yes(!b); return b; }
bool YES(bool b = true) { OUT(b ? "YES" : "NO"); return b; }
bool NO(bool b = true) { YES(!b); return b; }
#ifdef ONLINE_JUDGE
#define debug(...) (void(0))
#endif
template <class T> struct Compress {
private:
std::vector<T> vs;
bool built = false;
public:
Compress() = default;
explicit Compress(const std::vector<T>& vs) : vs(vs) {}
template <class InputIterator> Compress(InputIterator first, InputIterator last) : vs(first, last) {}
void reserve(size_t n) { vs.reserve(n); }
template <class... Ts> void add(const Ts&... xs) {
(vs.push_back(xs), ...);
built = false;
}
void build() {
std::sort(vs.begin(), vs.end());
vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
built = true;
}
int rank(const T& x) const {
assert(built);
return (int)(lower_bound(vs.begin(), vs.end(), x) - vs.begin());
}
const T& operator[](size_t i) const {
assert(built && i < vs.size());
return vs[i];
}
bool exists(const T& x) const {
assert(built);
size_t i = this->rank(x);
return i < this->size() && this->operator[](i) == x;
}
size_t size() const {
assert(built);
return vs.size();
}
static std::vector<int> compressed(const std::vector<T>& vs) {
Compress<T> cp(vs);
cp.build();
std::vector<int> res;
res.reserve(vs.size());
for (const auto& x : vs) res.push_back(cp.rank(x));
return res;
}
};
struct BitVector {
private:
int n, b;
bool built = false;
vector<u64> bit, sum;
public:
explicit BitVector(int n) : n(n) {
b = (n >> 6) + 1;
bit.resize(b);
sum.resize(b + 1);
}
void set(int i) { bit[i >> 6] |= 1ULL << (i & 63), built = false; }
void flip(int i) { bit[i >> 6] ^= 1ULL << (i & 63), built = false; }
bool get(int i) const { return bit[i >> 6] >> (i & 63) & 1; }
bool operator[](int i) const { return get(i); }
void build() {
built = true;
for (int i = 0; i < b; i++) sum[i + 1] = sum[i] + std::popcount(bit[i]);
}
int rank(int i) const {
assert(built);
return sum[i >> 6] + std::popcount(bit[i >> 6] & ((1ULL << (i & 63)) - 1));
}
int rank(bool x, int i) const { return x ? rank(i) : i - rank(i); }
int rank(bool x, int l, int r) const { return rank(x, r) - rank(x, l); }
};
template <class T> struct WaveletMatrix {
private:
const int LOG = 25;
int N;
vector<BitVector> bitvector;
vector<int> mid;
Compress<T> cp;
void build(vector<T> v) {
cp = Compress<T>(v);
cp.build();
for (auto& e : v) e = cp.rank(e);
N = v.size();
bitvector.assign(LOG, BitVector(N));
mid.resize(LOG);
vector<T> v0(N), v1(N);
for (int it = LOG - 1; it >= 0; it--) {
int l = 0, r = 0;
for (int i = 0; i < N; i++) {
if (v[i] >> it & 1) {
v1[r++] = v[i];
bitvector[it].set(i);
} else {
v0[l++] = v[i];
}
}
bitvector[it].build();
mid[it] = l;
v.swap(v0);
for (int i = 0; i < r; i++) v[i + l] = v1[i];
}
}
public:
explicit WaveletMatrix(const vector<T>& v) { build(v); }
T access(int p) const {
assert(0 <= p && p < N);
int res = 0;
for (int i = LOG - 1; i >= 0; i--) {
if (bitvector[i].get(p)) {
p = bitvector[i].rank(true, p) + mid[i];
res |= 1 << i;
} else {
p = bitvector[i].rank(false, p);
}
}
return cp[res];
}
int count(int l, int r, const T& x) const {
assert(0 <= l && l <= r && r <= N);
if (!cp.exists(x)) return 0;
int v = cp.rank(x);
for (int it = LOG - 1; it >= 0; it--) {
if (v >> it & 1) {
l = mid[it] + bitvector[it].rank(true, l);
r = mid[it] + bitvector[it].rank(true, r);
} else {
l = bitvector[it].rank(false, l);
r = bitvector[it].rank(false, r);
}
}
return r - l;
}
T kth_smallest(int l, int r, int k) const {
assert(0 <= l && l <= r && r <= N);
assert(0 <= k && k < r - l);
int res = 0;
for (int it = LOG - 1; it >= 0; it--) {
int cnt0 = bitvector[it].rank(false, l, r);
if (k < cnt0) {
l = bitvector[it].rank(false, l);
r = bitvector[it].rank(false, r);
} else {
l = mid[it] + bitvector[it].rank(true, l);
r = mid[it] + bitvector[it].rank(true, r);
res |= 1 << it;
k -= cnt0;
}
}
return cp[res];
}
T kth_largest(int l, int r, int k) const { return kth_smallest(l, r, r - l - 1 - k); }
int range_freq(int l, int r, const T& upper) const {
assert(0 <= l && l <= r && r <= N);
int v = cp.rank(upper);
int res = 0;
for (int it = LOG - 1; it >= 0; it--) {
if (v >> it & 1) {
res += bitvector[it].rank(false, l, r);
l = mid[it] + bitvector[it].rank(true, l);
r = mid[it] + bitvector[it].rank(true, r);
} else {
l = bitvector[it].rank(false, l);
r = bitvector[it].rank(false, r);
}
}
return res;
}
int range_freq(int l, int r, const T& lower, const T& upper) const { return range_freq(l, r, upper) - range_freq(l, r, lower); }
};
void run_case() {
INT(N);
VEC(int, A, N);
WaveletMatrix<int> wm(A);
INT(Q);
while (Q--) {
INT(l, r, x);
l--;
ll ans = 1e18;
if (wm.count(l, r, x)) ans = 0;
{
int cnt = wm.range_freq(l, r, x);
if (cnt != 0) {
chmin<ll>(ans, x-wm.kth_smallest(l, r, cnt - 1));
}
if (cnt != r - l) {
chmin<ll>(ans, wm.kth_smallest(l, r, cnt) - x);
}
}
OUT(ans);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::fixed(std::cout).precision(16);
ll t = 1;
while (t--) run_case();
}