結果
| 問題 | No.1332 Range Nearest Query |
| ユーザー |
 Kude
|
| 提出日時 | 2021-01-08 23:05:05 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,700 bytes |
| コンパイル時間 | 2,393 ms |
| コンパイル使用メモリ | 214,244 KB |
| 実行使用メモリ | 25,248 KB |
| 最終ジャッジ日時 | 2024-04-28 04:53:54 |
| 合計ジャッジ時間 | 8,253 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
10,624 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
ソースコード
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define chmax(a, b) a = max(a, b)
template<class T>
void chmin(T& a, const T& b) {
a = min<T>(a, b);
}
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
struct Q {
int i;
int l, r, x;
bool operator<(Q& y) {
int bx = l / 550, by = y.l / 550;
return (bx < by) || (bx == by && r < y.r);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
VI x(n);
rep(i, n) cin >> x[i];
int q;
cin >> q;
vector<Q> qs(q);
rep(i, q) {
qs[i].i = i;
cin >> qs[i].l >> qs[i].r >> qs[i].x;
qs[i].l--;
}
sort(all(qs));
int cur_b = -1, blast = -1;
VI ans(q);
set<int> s;
int p = -1;
rep(i, q) {
int l = qs[i].l, r = qs[i].r, z = qs[i].x;
int b = l / 550;
if (b != cur_b) {
cur_b = b;
s.clear();
blast = 550 * (b + 1);
p = blast;
}
while(p < r) s.insert(x[p++]);
auto it = s.lower_bound(z);
int tans = 1001001001;
if (it != s.end()) {
chmin(tans, *it - z);
}
if (it != s.begin()) {
it--;
chmin(tans, z - *it);
}
for(int j = l; j < min({blast, n, r}); ++j) {
chmin(tans, abs(x[j] - z));
}
ans[qs[i].i] = tans;
}
rep(i, q) cout << ans[i] << '\n';
}