結果
問題 | No.1332 Range Nearest Query |
ユーザー |
![]() |
提出日時 | 2021-01-08 23:16:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,779 bytes |
コンパイル時間 | 3,257 ms |
コンパイル使用メモリ | 202,152 KB |
実行使用メモリ | 94,388 KB |
最終ジャッジ日時 | 2024-11-16 17:36:37 |
合計ジャッジ時間 | 113,243 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 TLE * 30 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("unroll-loops")#pragma GCC optimize("Ofast")#include <bits/stdc++.h>using namespace std;const int INF = 1000000000;template <typename T>struct binary_indexed_tree{int N;vector<T> BIT;binary_indexed_tree(int n){N = 1;while (N < n){N *= 2;}BIT = vector<T>(N + 1, 0);}void add(int i, T x){i++;while (i <= N){BIT[i] += x;i += i & -i;}}T sum(int i){T ans = 0;while (i > 0){ans += BIT[i];i -= i & -i;}return ans;}T sum(int L, int R){return sum(R) - sum(L);}T all(){return BIT[N];}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;vector<int> X(N);for (int i = 0; i < N; i++){cin >> X[i];}vector<int> X2 = X;sort(X2.begin(), X2.end());int Q;cin >> Q;vector<int> l(Q), r(Q), x(Q);for (int i = 0; i < Q; i++){cin >> l[i] >> r[i] >> x[i];l[i]--;}vector<int> tv(Q, INF), fv(Q, -1);while (true){vector<int> mid(Q, -2);bool update = false;for (int i = 0; i < Q; i++){if (tv[i] - fv[i] > 1){mid[i] = (tv[i] + fv[i] + 2) / 2 - 1;update = true;}}if (!update){break;}vector<vector<int>> padd(N);for (int i = 0; i < N; i++){int p = lower_bound(X2.begin(), X2.end(), X[i]) - X2.begin();padd[i].push_back(p);}vector<vector<tuple<int, int, int>>> add(N);vector<vector<tuple<int, int, int>>> sub(N);for (int i = 0; i < Q; i++){if (mid[i] != -2){int L = x[i] - mid[i];int R = x[i] + mid[i];int Lp = lower_bound(X2.begin(), X2.end(), L) - X2.begin();int Rp = upper_bound(X2.begin(), X2.end(), R) - X2.begin();if (l[i] > 0){sub[l[i] - 1].push_back(make_tuple(Lp, Rp, i));}add[r[i] - 1].push_back(make_tuple(Lp, Rp, i));}}binary_indexed_tree<int> BIT(N);vector<int> cnt(Q, 0);for (int i = 0; i < N; i++){for (int j : padd[i]){BIT.add(j, 1);}int addcnt = add[i].size();for (int j = 0; j < addcnt; j++){int L = get<0>(add[i][j]);int R = get<1>(add[i][j]);int id = get<2>(add[i][j]);cnt[id] += BIT.sum(L, R);}int subcnt = sub[i].size();for (int j = 0; j < subcnt; j++){int L = get<0>(sub[i][j]);int R = get<1>(sub[i][j]);int id = get<2>(sub[i][j]);cnt[id] -= BIT.sum(L, R);}}for (int i = 0; i < Q; i++){if (mid[i] != -2){if (cnt[i] == 0){fv[i] = mid[i];} else {tv[i] = mid[i];}}}}for (int i = 0; i < Q; i++){cout << tv[i] << "\n";}}