結果

問題 No.1332 Range Nearest Query
ユーザー lmori
提出日時 2024-10-15 01:32:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 531 ms / 2,500 ms
コード長 12,227 bytes
コンパイル時間 5,367 ms
コンパイル使用メモリ 301,212 KB
実行使用メモリ 37,504 KB
最終ジャッジ日時 2024-10-15 01:33:13
合計ジャッジ時間 24,391 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using ull = unsigned long long;
using ld = long double;
using int128 = __int128_t;
#define all(x) (x).begin(), (x).end()
#define EPS 1e-8
#define uniqv(v) v.erase(unique(all(v)), v.end())
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define log(x) cout << x << endl
#define logfixed(x) cout << fixed << setprecision(10) << x << endl;
#define logy(bool) \
if (bool) { \
cout << "Yes" << endl; \
} else { \
cout << "No" << endl; \
}
ostream &operator<<(ostream &dest, __int128_t value) {
ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(ios_base::badbit);
}
}
return dest;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
os << *itr;
++itr;
if (itr != set_var.end()) os << " ";
itr--;
}
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
os << itr->first << " -> " << itr->second << "\n";
}
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
os << "(" << pair_var.first << ", " << pair_var.second << ")";
return os;
}
void out() { cout << '\n'; }
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
cout << a;
(cout << ... << (cout << ' ', b));
cout << '\n';
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v) is >> in;
return is;
}
inline void in(void) { return; }
template <typename First, typename... Rest>
void in(First &first, Rest &...rest) {
cin >> first;
in(rest...);
return;
}
template <typename T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
vector<lint> dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
vector<lint> dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<lint> dx4 = {1, 0, -1, 0};
vector<lint> dy4 = {0, 1, 0, -1};
#pragma endregion
template <class T>
class BitVector {
private:
unsigned n, cur, p;
vector<unsigned> acc, bit;
vector<T> srsum;
public:
BitVector() {
}
BitVector(vector<bool> &b) {
cur = 0;
n = b.size();
acc.resize((n >> 5) + 2, 0);
bit.resize((n >> 5) + 2, 0);
srsum.resize(n + 1, 0);
for (int i = 0; i < n; i++) {
if (!(i & 31)) {
cur++;
acc[cur] = acc[cur - 1];
}
if (b[i]) {
acc[cur] += int(b[i]);
bit[cur - 1] |= (1U << (32 - (i & 31) - 1));
}
}
}
inline void srsum_set(const vector<T> &v) {
for (int i = 0; i < n; i++) {
srsum[i + 1] = srsum[i] + v[i];
}
}
inline unsigned rank(unsigned k) {
if (!(k & 31)) return acc[k >> 5];
return acc[k >> 5] + __builtin_popcount(bit[k >> 5] >> (32 - (k & 31)));
}
inline T rank_srsum(unsigned k) {
return srsum[k];
}
inline bool access(unsigned k) {
return (rank(k + 1) - rank(k)) == 1;
}
};
template <class T>
class WaveletMatrix {
private:
unsigned n;
unsigned bitsize;
vector<BitVector<T>> b;
vector<unsigned> zero;
vector<int> stInd;
vector<unsigned> compressed;
vector<T> cmp;
vector<long long> sum;
T MI, MA;
// v[l,r) k
long long rank_sum(unsigned l, unsigned r, unsigned k) {
long long less_sum = 0;
for (unsigned i = 0; i < bitsize and l < r; i++) {
const unsigned rank1_l = b[i].rank(l);
const unsigned rank1_r = b[i].rank(r);
const unsigned rank0_l = l - rank1_l;
const unsigned rank0_r = r - rank1_r;
if (k & (1U << (bitsize - i - 1))) {
less_sum += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
l = zero[i] + rank1_l;
r = zero[i] + rank1_r;
} else {
l = rank0_l;
r = rank0_r;
}
}
return less_sum;
}
// v[l,r) k
unsigned rank_less(unsigned l, unsigned r, T k) {
unsigned less = 0;
for (unsigned i = 0; i < bitsize and l < r; i++) {
const unsigned rank1_l = b[i].rank(l);
const unsigned rank1_r = b[i].rank(r);
const unsigned rank0_l = l - rank1_l;
const unsigned rank0_r = r - rank1_r;
if (k & (1U << (bitsize - i - 1))) {
less += (rank0_r - rank0_l);
l = zero[i] + rank1_l;
r = zero[i] + rank1_r;
} else {
l = rank0_l;
r = rank0_r;
}
}
return less;
}
// v[l,r) k
pair<long long, long long> rank_less_sum(unsigned l, unsigned r, T k) {
long long less = 0;
long long less_sum = 0;
for (unsigned i = 0; i < bitsize and l < r; i++) {
const unsigned rank1_l = b[i].rank(l);
const unsigned rank1_r = b[i].rank(r);
const unsigned rank0_l = l - rank1_l;
const unsigned rank0_r = r - rank1_r;
if (k & (1U << (bitsize - i - 1))) {
less += (rank0_r - rank0_l);
less_sum += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
l = zero[i] + rank1_l;
r = zero[i] + rank1_r;
} else {
l = rank0_l;
r = rank0_r;
}
}
return {less, less_sum};
}
inline unsigned compress(const T &x) {
return lower_bound(cmp.begin(), cmp.end(), x) - begin(cmp);
}
public:
//
WaveletMatrix() {}
WaveletMatrix(vector<T> v) {
MI = numeric_limits<T>::min();
MA = numeric_limits<T>::max();
n = v.size();
cmp = v;
sort(cmp.begin(), cmp.end());
cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
compressed.resize(n);
sum.resize(n + 1);
vector<T> tmp(n);
vector<unsigned> tmpc(n);
unsigned size_mx = v.size();
for (unsigned i = 0; i < n; i++) {
compressed[i] = distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), v[i]));
sum[i + 1] = sum[i] + v[i];
}
stInd.resize(cmp.size() + 1, -1);
bitsize = bit_width(size_mx);
b.resize(bitsize);
zero.resize(bitsize, 0);
vector<bool> bit(n, 0);
for (unsigned i = 0; i < bitsize; i++) {
for (unsigned j = 0; j < n; j++) {
bit[j] = compressed[j] & (1U << (bitsize - i - 1));
zero[i] += unsigned(!bit[j]);
tmp[j] = v[j];
tmpc[j] = compressed[j];
}
b[i] = BitVector<T>(bit);
int cur = 0;
for (unsigned j = 0; j < n; j++) {
if (!bit[j]) {
v[cur] = tmp[j];
compressed[cur] = tmpc[j];
cur++;
}
}
for (unsigned j = 0; j < n; j++) {
if (bit[j]) {
v[cur] = tmp[j];
compressed[cur] = tmpc[j];
cur++;
}
}
b[i].srsum_set(v);
}
for (unsigned i = 0; i < n; i++) {
if (stInd[compressed[i]] == -1) {
stInd[compressed[i]] = i;
}
}
}
// get v[k]
T access(unsigned k) {
unsigned res = 0;
unsigned cur = k;
for (unsigned i = 0; i < bitsize; i++) {
if (b[i].access(cur)) {
res |= (1U << (bitsize - i - 1));
cur = zero[i] + b[i].rank(cur);
} else {
cur -= b[i].rank(cur);
}
}
return cmp[res];
}
// v[0,k) c
unsigned rank(unsigned k, T c) {
c = compress(c);
unsigned cur = k;
if (stInd[c] == -1) {
return 0;
}
for (unsigned i = 0; i < bitsize; i++) {
if (c & (1U << (bitsize - i - 1))) {
cur = zero[i] + b[i].rank(cur);
} else {
cur -= b[i].rank(cur);
}
}
return cur - stInd[c];
}
// v[l,r) k(1-origin)
T kth_smallest(unsigned l, unsigned r, unsigned k) {
unsigned res = 0;
for (unsigned i = 0; i < bitsize; i++) {
unsigned num1 = b[i].rank(r) - b[i].rank(l);
unsigned num0 = r - l - num1;
if (num0 < k) {
res |= (1ULL << (bitsize - i - 1));
l = zero[i] + b[i].rank(l);
r = zero[i] + b[i].rank(r);
k -= num0;
} else {
l -= b[i].rank(l);
r -= b[i].rank(r);
}
}
return cmp[res];
}
// v[l,r) k(1-origin)
T kth_largest(unsigned l, unsigned r, unsigned k) {
return kth_smallest(l, r, r - l - k + 1);
}
// v[l,r]k
long long kth_ascending_sum(unsigned l, unsigned r, unsigned k) {
long long res = 0;
unsigned val = 0;
for (unsigned i = 0; i < bitsize; i++) {
const unsigned rank1_l = b[i].rank(l);
const unsigned rank1_r = b[i].rank(r);
const unsigned rank0_l = l - rank1_l;
const unsigned rank0_r = r - rank1_r;
const unsigned num1 = rank1_r - rank1_l;
const unsigned num0 = rank0_r - rank0_l;
if (num0 < k) {
val |= (1ULL << (bitsize - i - 1));
res += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
l = zero[i] + rank1_l;
r = zero[i] + rank1_r;
k -= num0;
} else {
l = rank0_l;
r = rank0_r;
}
}
res += int64_t(cmp[val]) * (k);
return res;
}
// v[l,r]k
long long kth_descending_sum(unsigned l, unsigned r, unsigned k) {
return range_sum(l, r) - kth_ascending_sum(l, r, r - l - k);
}
// v[l,r) [mink,maxk)
unsigned range_freq(unsigned l, unsigned r, T mink, T maxk) {
mink = compress(mink);
maxk = compress(maxk);
if (mink == 0) {
return rank_less(l, r, maxk);
}
return rank_less(l, r, maxk) - rank_less(l, r, mink);
}
// v[l,r)
long long range_sum(unsigned l, unsigned r) {
return sum[r] - sum[l];
}
// v[l,r) [mink,maxk)
long long range_sum(unsigned l, unsigned r, T mink, T maxk) {
mink = compress(mink);
maxk = compress(maxk);
return rank_sum(l, r, maxk) - rank_sum(l, r, mink);
}
// v[l,r) ∑|v[i]-d|
long long range_abs(unsigned l, unsigned r, T d) {
T dnum = rank(r, d) - rank(l, d);
T dsum = d * dnum;
T asum = range_sum(l, r);
auto p = rank_less_sum(l, r, compress(d));
T less = p.first;
T less_sum = p.second;
T more = r - l - dnum - less;
T more_sum = asum - dsum - less_sum;
return d * less + more_sum - less_sum - (d * more);
}
// v[l,r)val
T prev_value(unsigned l, unsigned r, T val) {
int num = range_freq(l, r, MI, val);
if (num == 0) {
return MA;
} else {
return kth_smallest(l, r, num);
}
}
// v[l,r)val
T next_value(unsigned l, unsigned r, T val) {
int num = range_freq(l, r, MI, val);
if (num == r - l) {
return MI;
} else {
return kth_smallest(l, r, num + 1);
}
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n;
in(n);
vector<int> a(n);
in(a);
WaveletMatrix w(a);
int q;
in(q);
rep(i, q) {
int l, r, x;
in(l, r, x);
l--;
int nex = w.next_value(l, r, x);
int pre = w.prev_value(l, r, x);
out(min(abs(x - nex), abs(pre - x)));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0