結果
| 問題 | No.3446 Range Adjacent Differences |
| ユーザー |
 fiblonaria
|
| 提出日時 | 2026-03-14 15:34:54 |
| 言語 | C++14 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,877 bytes |
| 記録 | |
| コンパイル時間 | 1,875 ms |
| コンパイル使用メモリ | 204,664 KB |
| 実行使用メモリ | 29,952 KB |
| 最終ジャッジ日時 | 2026-03-14 15:35:39 |
| 合計ジャッジ時間 | 44,691 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 WA * 2 TLE * 12 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
/*
問題の管理対象
----------------
現在区間 [curL, curR] に対して
1. 各値の出現回数 freq[id]
2. 出現回数 >= 1 の distinct 値の集合 active
3. active を昇順に並べたときの隣接差 multiset gaps
4. 重複によって生じる差 0 の個数 zeroGapCount
を管理する。
クエリ
- type == 'L' : C の要素で X 以下の最大値
- type == 'R' : C の要素で X 以上の最小値
*/
/*------------------------------------------------------------
| Hilbert Order
*-----------------------------------------------------------*/
static long long hilbert_order(int x, int y, int pow = 21, int rot = 0) {
if (pow == 0) return 0;
int hpow = 1 << (pow - 1);
int seg = (x < hpow)
? ((y < hpow) ? 0 : 3)
: ((y < hpow) ? 1 : 2);
seg = (seg + rot) & 3;
static const int rotate_delta[4] = {3, 0, 0, 1};
int nx = x & (x ^ hpow);
int ny = y & (y ^ hpow);
int nrot = (rot + rotate_delta[seg]) & 3;
long long sub_size = 1LL << (2 * pow - 2);
long long ans = 1LL * seg * sub_size;
long long add = hilbert_order(nx, ny, pow - 1, nrot);
ans += (seg == 1 || seg == 2) ? add : (sub_size - add - 1);
return ans;
}
/*------------------------------------------------------------
| 64分木系の高速順序集合
| 0..n-1 の整数について insert / erase / contains / next / prev
*-----------------------------------------------------------*/
struct FastSet {
int n;
vector<vector<unsigned long long>> seg;
FastSet() : n(0) {}
explicit FastSet(int n_) { init(n_); }
void init(int n_) {
n = n_;
seg.clear();
seg.push_back(vector<unsigned long long>((n + 63) >> 6, 0ULL));
while (seg.back().size() > 1) {
int m = (int)seg.back().size();
seg.push_back(vector<unsigned long long>((m + 63) >> 6, 0ULL));
}
}
bool contains(int x) const {
return (seg[0][x >> 6] >> (x & 63)) & 1ULL;
}
void insert(int x) {
for (int h = 0; h < (int)seg.size(); h++) {
seg[h][x >> 6] |= 1ULL << (x & 63);
x >>= 6;
}
}
void erase(int x) {
for (int h = 0; h < (int)seg.size(); h++) {
auto &block = seg[h][x >> 6];
block &= ~(1ULL << (x & 63));
if (block) break;
x >>= 6;
}
}
// x 以上の最小の存在要素。なければ n を返す
int next(int x) const {
if (x < 0) x = 0;
if (x >= n) return n;
for (int h = 0; h < (int)seg.size(); h++) {
int i = x >> 6;
if (i >= (int)seg[h].size()) break;
unsigned long long d = seg[h][i] >> (x & 63);
if (d == 0) {
i++;
while (i < (int)seg[h].size() && seg[h][i] == 0) i++;
if (i == (int)seg[h].size()) return n;
x = i << 6;
} else {
x += __builtin_ctzll(d);
}
for (int g = h - 1; g >= 0; g--) {
x <<= 6;
unsigned long long d2 = seg[g][x >> 6];
x += __builtin_ctzll(d2);
}
return x;
}
return n;
}
// x 以下の最大の存在要素。なければ -1 を返す
int prev(int x) const {
if (x < 0) return -1;
if (x >= n) x = n - 1;
for (int h = 0; h < (int)seg.size(); h++) {
int i = x >> 6;
if (i < 0) return -1;
unsigned long long d;
if ((x & 63) == 63) {
d = seg[h][i];
} else {
d = seg[h][i] & ((1ULL << ((x & 63) + 1)) - 1);
}
if (d == 0) {
i--;
while (i >= 0 && seg[h][i] == 0) i--;
if (i < 0) return -1;
x = (i << 6) + 63;
} else {
x = (i << 6) + 63 - __builtin_clzll(d);
}
for (int g = h - 1; g >= 0; g--) {
x <<= 6;
int block = x >> 6;
unsigned long long d2 = seg[g][block];
x += 63 - __builtin_clzll(d2);
}
return x;
}
return -1;
}
};
/*------------------------------------------------------------
| Query
*-----------------------------------------------------------*/
struct Query {
int l, r, x, id;
char type;
long long ord;
};
/*------------------------------------------------------------
| 1個だけ erase する補助
*-----------------------------------------------------------*/
static inline void erase_one(multiset<int>& ms, int value) {
auto it = ms.find(value);
if (it != ms.end()) ms.erase(it);
}
/*------------------------------------------------------------
| 現在区間の状態管理
*-----------------------------------------------------------*/
class RangeManager {
public:
RangeManager(const vector<int>& compressedToValue, int compressedSize)
: values(compressedToValue),
freq(compressedSize, 0),
active(compressedSize),
zeroGapCount(0) {}
void addCompressedValue(int id) {
// すでに存在する値なら、差 0 が1個増えるだけ
if (freq[id] >= 1) {
freq[id]++;
zeroGapCount++;
return;
}
// 初出現: active に入れる
int rightId = active.next(id);
int leftId = active.prev(id);
bool hasLeft = (leftId != -1);
bool hasRight = (rightId != (int)values.size());
int x = values[id];
if (hasLeft && hasRight) {
int leftValue = values[leftId];
int rightValue = values[rightId];
erase_one(gaps, rightValue - leftValue);
gaps.insert(x - leftValue);
gaps.insert(rightValue - x);
} else if (hasLeft) {
int leftValue = values[leftId];
gaps.insert(x - leftValue);
} else if (hasRight) {
int rightValue = values[rightId];
gaps.insert(rightValue - x);
}
active.insert(id);
freq[id] = 1;
}
void removeCompressedValue(int id) {
// まだ複数個あるなら、差 0 が1個減るだけ
if (freq[id] >= 2) {
freq[id]--;
zeroGapCount--;
return;
}
// 最後の1個を消す: active から除去
int leftId = active.prev(id - 1);
int rightId = active.next(id + 1);
bool hasLeft = (leftId != -1);
bool hasRight = (rightId != (int)values.size());
int x = values[id];
if (hasLeft && hasRight) {
int leftValue = values[leftId];
int rightValue = values[rightId];
erase_one(gaps, x - leftValue);
erase_one(gaps, rightValue - x);
gaps.insert(rightValue - leftValue);
} else if (hasLeft) {
int leftValue = values[leftId];
erase_one(gaps, x - leftValue);
} else if (hasRight) {
int rightValue = values[rightId];
erase_one(gaps, rightValue - x);
}
active.erase(id);
freq[id] = 0;
}
int answer(int X, char type) const {
if (type == 'L') {
int best = -1;
// X >= 1 なので 0 は常に候補になりうる
if (zeroGapCount > 0) best = 0;
auto it = gaps.upper_bound(X);
if (it != gaps.begin()) {
--it;
best = max(best, *it);
}
return best;
} else {
auto it = gaps.lower_bound(X);
if (it == gaps.end()) return -1;
return *it;
}
}
private:
const vector<int>& values; // 圧縮ID -> 元の値
vector<int> freq;
FastSet active; // 現在存在する distinct 値の圧縮ID集合
multiset<int> gaps; // distinct 値間の隣接差
int zeroGapCount; // 差0の個数
};
/*------------------------------------------------------------
| main
*-----------------------------------------------------------*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
// 座標圧縮
vector<int> sortedValues = A;
sort(sortedValues.begin(), sortedValues.end());
sortedValues.erase(unique(sortedValues.begin(), sortedValues.end()), sortedValues.end());
int M = (int)sortedValues.size();
vector<int> compressedA(N);
for (int i = 0; i < N; i++) {
compressedA[i] = lower_bound(sortedValues.begin(), sortedValues.end(), A[i]) - sortedValues.begin();
}
// クエリ読み込み
vector<Query> queries(Q);
for (int i = 0; i < Q; i++) {
int L, R, X;
char c;
cin >> L >> R >> X >> c;
--L;
--R;
queries[i] = {L, R, X, i, c, hilbert_order(L, R)};
}
sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
return a.ord < b.ord;
});
RangeManager manager(sortedValues, M);
vector<int> answers(Q, -1);
int curL = 0;
int curR = -1;
for (const auto& q : queries) {
while (curL > q.l) manager.addCompressedValue(compressedA[--curL]);
while (curR < q.r) manager.addCompressedValue(compressedA[++curR]);
while (curL < q.l) manager.removeCompressedValue(compressedA[curL++]);
while (curR > q.r) manager.removeCompressedValue(compressedA[curR--]);
answers[q.id] = manager.answer(q.x, q.type);
}
for (int i = 0; i < Q; i++) {
cout << answers[i] << '\n';
}
return 0;
}