結果

問題 No.1332 Range Nearest Query
ユーザー outlineoutline
提出日時 2021-01-08 22:26:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 596 ms / 2,500 ms
コード長 6,931 bytes
コンパイル時間 2,266 ms
コンパイル使用メモリ 143,856 KB
最終ジャッジ日時 2025-01-17 12:43:18
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <array>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;
template<class T>
inline bool chmax(T& x, T y){
if(x < y){
x = y;
return true;
}
return false;
}
template<class T>
inline bool chmin(T& x, T y){
if(x > y){
x = y;
return true;
}
return false;
}
struct SuccinctIndexableDictionary {
size_t length, blocks;
vector<unsigned> bit, sum;
SuccinctIndexableDictionary() = default;
SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {
bit.assign(blocks, 0U);
sum.assign(blocks, 0U);
}
void set(int k){
bit[k >> 5] |= 1U << (k & 31);
}
void build(){
sum[0] = 0U;
for(int i = 1; i < blocks; ++i){
sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
}
}
bool operator[](int k){
return (bool((bit[k >> 5] >> (k & 31)) & 1));
}
int rank(int k){
return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
}
// f : bit flag
int rank(bool f, int k){
return (f ? rank(k) : k - rank(k));
}
};
template<typename T, int MAXLOG>
struct WaveletMatrix {
size_t length;
SuccinctIndexableDictionary matrix[MAXLOG];
int mid[MAXLOG];
WaveletMatrix() = default;
WaveletMatrix(vector<T> v) : length(v.size()) {
vector<T> zero(length), one(length);
for(int level = MAXLOG - 1; level >= 0; --level){
matrix[level] = SuccinctIndexableDictionary(length + 1);
int left = 0, right = 0;
for(int i = 0; i < length; ++i){
if(((v[i] >> level) & 1)){
matrix[level].set(i);
one[right++] = v[i];
}
else{
zero[left++] = v[i];
}
}
mid[level] = left;
matrix[level].build();
v.swap(zero);
for(int i = 0; i < right; ++i){
v[left + i] = one[i];
}
}
}
pair<int, int> succ(bool f, int l, int r, int level){
return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f};
}
T access(int k){
T ret = 0;
for(int level = MAXLOG - 1; level >= 0; --level){
bool f = matrix[level][k];
if(f) ret |= T(1) << level;
k = matrix[level].rank(f, k) + mid[level] * f;
}
return ret;
}
T operator[](const int& k){
return access(k);
}
int rank(const T& x, int r){
int l = 0;
for(int level = MAXLOG - 1; level >= 0; --level){
tie(l, r) = succ((x >> level) & 1, l, r, level);
}
return r - l;
}
T kth_smallest(int l, int r, int k){
assert(0 <= k && k < r - l);
T ret = 0;
for(int level = MAXLOG - 1; level >= 0; --level){
int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l);
bool f = cnt <= k;
if(f){
ret |= T(1) << level;
k -= cnt;
}
tie(l, r) = succ(f, l, r, level);
}
return ret;
}
T kth_largest(int l, int r, int k){
return kth_smallest(l, r, r - l - k - 1);
}
int range_freq(int l, int r, T upper){
int ret = 0;
for(int level = MAXLOG - 1; level >= 0; --level){
bool f = ((upper >> level) & 1);
if(f) ret += matrix[level].rank(false, r) - matrix[level].rank(false, l);
tie(l, r) = succ(f, l, r, level);
}
return ret;
}
int range_freq(int l, int r, T lower, T upper){
return range_freq(l, r, upper) - range_freq(l, r, lower);
}
T prev_value(int l, int r, T upper){
int cnt = range_freq(l, r, upper);
return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);
}
T next_value(int l, int r, T lower){
int cnt = range_freq(l, r, lower);
return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);
}
};
template<typename T, int MAXLOG>
struct CompressedWaveletMatrix {
WaveletMatrix<int, MAXLOG> mat;
vector<T> ys;
CompressedWaveletMatrix(const vector<T>& v) : ys(v) {
sort(begin(ys), end(ys));
ys.erase(unique(ys.begin(), ys.end()), ys.end());
vector<int> t(v.size());
for(int i = 0; i < (int)v.size(); ++i) t[i] = get(v[i]);
mat = WaveletMatrix<int, MAXLOG>(t);
}
inline int get(const T& x){
return lower_bound(begin(ys), end(ys), x) - begin(ys);
}
T access(int k){
return ys[mat.access(k)];
}
T operator[](const int& k){
return access(k);
}
int rank(const T& x, int r){
auto pos = get(x);
if(pos == ys.size() || ys[pos] != x) return 0;
return mat.rank(pos, r);
}
T kth_smallest(int l, int r, int k){
return ys[mat.kth_smallest(l, r, k)];
}
T kth_largest(int l, int r, int k){
return ys[mat.kth_largest(l, r, k)];
}
int range_freq(int l, int r, T upper){
return mat.range_freq(l, r, get(upper));
}
int range_freq(int l, int r, T lower, T upper){
return mat.range_freq(l, r, get(lower), get(upper));
}
T prev_value(int l, int r, T upper){
auto ret = mat.prev_value(l, r, get(upper));
return ret == -1 ? T(-1) : ys[ret];
}
T next_value(int l, int r, T lower){
auto ret = mat.next_value(l, r, get(lower));
return ret == -1 ? T(-1) : ys[ret];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q, l, r, x;
cin >> N;
vector<int> X(N);
for(int i = 0; i < N; ++i) cin >> X[i];
CompressedWaveletMatrix<int, 25> cwm(X);
cin >> Q;
for(int q = 0; q < Q; ++q){
cin >> l >> r >> x;
--l;
if(cwm.range_freq(l, r, x, x + 1)){
cout << 0 << '\n';
}
else{
int prv = cwm.prev_value(l, r, x);
int nxt = cwm.next_value(l, r, x);
int ans = INF;
if(prv != -1) chmin(ans, x - prv);
if(nxt != -1) chmin(ans, nxt - x);
cout << ans << '\n';
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0