結果
問題 | No.1332 Range Nearest Query |
ユーザー |
![]() |
提出日時 | 2021-01-08 23:15:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 486 ms / 2,500 ms |
コード長 | 2,327 bytes |
コンパイル時間 | 2,573 ms |
コンパイル使用メモリ | 190,160 KB |
実行使用メモリ | 29,852 KB |
最終ジャッジ日時 | 2024-11-16 17:22:54 |
合計ジャッジ時間 | 23,842 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#include <atcoder/segtree>#include <bits/stdc++.h>using namespace std;using namespace atcoder;#define INF_LL 100000000000000000LL#define INF 2000000000#define MOD 1000000007#define ll long long#define all(x) x.begin(), x.end()#define REP(i, a, b) for(int i = a; i < b; i++)#define rep(i, n) REP(i, 0, n)#define int long long// typedef float double;// typedef priority_queue prique;typedef pair<ll, ll> P;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<P> vp;typedef vector<ll> vl;typedef vector<vi> matrix;int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};int sign[2] = {1, -1};template <class T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}template <class T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}ll modpow(ll a, ll b, ll m) {if(b == 0)return 1;ll t = modpow(a, b / 2, m);if(b & 1) {return (t * t % m) * a % m;} else {return t * t % m;}}struct edge {int to;ll cost;edge(int t, ll c) { to = t, cost = c; }};typedef vector<vector<edge>> graph;// using mint = modint998244353;int minop(int x, int y) {return min(x, y);}int maxop(int x, int y) {return max(x, y);}int mine() {return INF;}int maxe() {return -INF;}signed main() {int n, q;cin >> n;vector<pair<int, int>> a(n);rep(i, n) {cin >> a[i].first;a[i].second = i;}segtree<int, maxop, maxe> seg1(n);segtree<int, minop, mine> seg2(n);rep(i, n) seg2.set(i, a[i].first);sort(all(a));cin >> q;vector<tuple<int, int, int, int>> query(q);rep(i, q){int l, r, x;cin >> l >> r >> x;query[i] = {x, l, r, i};}sort(all(query));int idx = 0;rep(i, q){int x, l, r, g;tie(x, l, r, g) = query[i];while(idx < n && x > a[idx].first){seg1.set(a[idx].second, seg2.get(a[idx].second));seg2.set(a[idx].second, mine());idx++;}get<0>(query[i]) = min(seg2.prod(l - 1, r) - x, x - seg1.prod(l - 1, r));}sort(begin(query), end(query), [](const auto &x, const auto &y){return get<3>(x) < get<3>(y);});rep(i, q){cout << get<0>(query[i]) << endl;}return 0;}