結果
問題 | No.1332 Range Nearest Query |
ユーザー |
![]() |
提出日時 | 2021-01-08 22:09:44 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 868 ms / 2,500 ms |
コード長 | 1,853 bytes |
コンパイル時間 | 2,147 ms |
コンパイル使用メモリ | 90,224 KB |
実行使用メモリ | 88,848 KB |
最終ジャッジ日時 | 2024-11-16 12:28:41 |
合計ジャッジ時間 | 27,849 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#include <complex>#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define all(x) (x).begin(),(x).end()#define inf 1e18#define mod 1000000007using namespace std;typedef long long llint;typedef long long ll;typedef pair<llint, llint> P;struct SegTree{int size;vector<vector<llint> > seg;SegTree(){}SegTree(int size){this->size = size;seg.resize(1<<(size+1));}void init(){for(int i = 0; i < (1<<(size+1)); i++) sort(all(seg[i]));}void update(int i, llint val){i += (1 << size);seg[i].push_back(val);while(i > 1){i /= 2;seg[i].push_back(val);}}llint query(int a, int b, int k, int l, int r, llint x){if(b < l || r < a) return inf;if(a <= l && r <= b){llint ret = inf;int p = lower_bound(all(seg[k]), x) - seg[k].begin();if(p < seg[k].size()) chmin(ret, abs(seg[k][p] - x));if(p > 0) chmin(ret, abs(seg[k][p-1] - x));return ret;}llint lval = query(a, b, k*2, l, (l+r)/2, x);llint rval = query(a, b, k*2+1, (l+r)/2+1, r, x);return min(lval, rval);}llint query(int a, int b, ll x){return query(a, b, 1, 0, (1<<size)-1, x);}};ll n, Q;ll x[300005];SegTree seg(19);int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n;rep(i, 1, n){cin >> x[i];seg.update(i, x[i]);}seg.init();cin >> Q;ll l, r, x;rep(i, 1, Q){cin >> l >> r >> x;cout << seg.query(l, r, x) << "\n";}flush(cout);return 0;}