結果
問題 |
No.1332 Range Nearest Query
|
ユーザー |
![]() |
提出日時 | 2021-01-08 21:38:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,220 ms / 2,500 ms |
コード長 | 1,649 bytes |
コンパイル時間 | 1,771 ms |
コンパイル使用メモリ | 131,672 KB |
最終ジャッジ日時 | 2025-01-17 11:26:32 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <stack> #include <array> #include <list> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; int main() { int n; cin>>n; ll a[300030]; for(int i=0; i<n; i++) cin>>a[i]; int sz=1; while(sz<n) sz<<=1; vector<vector<int>> seg(sz*2); for(int i=0; i<n; i++){ int k=sz+i; seg[k].push_back(a[i]); while(k>1){ k>>=1; seg[k].push_back(a[i]); } } for(int i=0; i<2*sz; i++){ sort(seg[i].begin(), seg[i].end()); } int q; cin>>q; while(q--){ int l, r, x; cin>>l>>r>>x; l--; int l1=l, r1=r; l+=sz, r+=sz; int ans=1e9+7; for(;l<r; l>>=1, r>>=1){ if(r&1){ r--; int k=lower_bound(seg[r].begin(), seg[r].end(), x)-seg[r].begin(); if(k<seg[r].size()) ans=min(ans, seg[r][k]-x); if(k-1>=0) ans=min(ans, x-seg[r][k-1]); } if(l&1){ int k=lower_bound(seg[l].begin(), seg[l].end(), x)-seg[l].begin(); if(k<seg[l].size()) ans=min(ans, seg[l][k]-x); if(k-1>=0) ans=min(ans, x-seg[l][k-1]); l++; } } cout<<ans<<endl; } return 0; }