結果

問題 No.1332 Range Nearest Query
ユーザー 👑 NachiaNachia
提出日時 2021-01-12 21:43:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 273 ms / 2,500 ms
コード長 2,600 bytes
コンパイル時間 2,306 ms
コンパイル使用メモリ 211,960 KB
実行使用メモリ 21,120 KB
最終ジャッジ日時 2024-05-01 08:12:46
合計ジャッジ時間 14,899 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
10,880 KB
testcase_01 AC 5 ms
10,752 KB
testcase_02 AC 5 ms
10,752 KB
testcase_03 AC 242 ms
18,560 KB
testcase_04 AC 241 ms
18,432 KB
testcase_05 AC 233 ms
18,560 KB
testcase_06 AC 153 ms
20,524 KB
testcase_07 AC 152 ms
20,608 KB
testcase_08 AC 152 ms
20,524 KB
testcase_09 AC 153 ms
20,608 KB
testcase_10 AC 152 ms
20,564 KB
testcase_11 AC 153 ms
20,536 KB
testcase_12 AC 155 ms
20,580 KB
testcase_13 AC 156 ms
20,696 KB
testcase_14 AC 155 ms
20,520 KB
testcase_15 AC 152 ms
20,608 KB
testcase_16 AC 249 ms
21,120 KB
testcase_17 AC 256 ms
21,028 KB
testcase_18 AC 266 ms
20,980 KB
testcase_19 AC 260 ms
21,024 KB
testcase_20 AC 264 ms
21,060 KB
testcase_21 AC 269 ms
20,992 KB
testcase_22 AC 239 ms
21,120 KB
testcase_23 AC 251 ms
21,084 KB
testcase_24 AC 254 ms
20,984 KB
testcase_25 AC 273 ms
21,120 KB
testcase_26 AC 118 ms
19,848 KB
testcase_27 AC 123 ms
19,728 KB
testcase_28 AC 39 ms
12,312 KB
testcase_29 AC 41 ms
12,376 KB
testcase_30 AC 41 ms
12,268 KB
testcase_31 AC 36 ms
12,240 KB
testcase_32 AC 44 ms
12,316 KB
testcase_33 AC 45 ms
12,332 KB
testcase_34 AC 41 ms
12,568 KB
testcase_35 AC 40 ms
12,312 KB
testcase_36 AC 41 ms
12,184 KB
testcase_37 AC 42 ms
12,240 KB
testcase_38 AC 171 ms
17,024 KB
testcase_39 AC 78 ms
13,440 KB
testcase_40 AC 249 ms
20,864 KB
testcase_41 AC 117 ms
13,952 KB
testcase_42 AC 164 ms
17,024 KB
testcase_43 AC 131 ms
15,104 KB
testcase_44 AC 210 ms
18,048 KB
testcase_45 AC 187 ms
17,792 KB
testcase_46 AC 161 ms
15,744 KB
testcase_47 AC 185 ms
17,408 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

template<
  class S,
  S(*op)(S a,S b),
  S(*e)()
>
struct segtree {
  int N;
  vector<S> V;
  segtree(int n=0){
    N=1; while(N<n) N*=2;
    V.assign(N*2,e());
  }
  segtree(const vector<S>& v)
    : segtree(v.size()){
    rep(i,v.size()) V[N+i]=v[i];
    for(int i=N-1; i>=1; i--) V[i]=op(V[i*2],V[i*2+1]);
  }
  void set(int p,S v){
    p+=N; V[p]=v;
    while(p!=1){ p/=2; V[p]=op(V[p*2],V[p*2+1]); }
  }
  S get(int p){ return V[N+p]; }
  S prod(int l,int r){
    l+=N; r+=N;
    S resl=e(), resr=e();
    while(r-l){
      if(l&1) resl=op(resl,V[l++]);
      if(r&1) resr=op(V[--r],resr);
      l/=2; r/=2;
    }
    return op(resl,resr);
  }
  template<class Cmp>
  int max_right(int l,Cmp cmp){
    S x=e(); l+=N; int r=N+N;
    while(l<r){
      if(l&1){
        S tmp=op(x,V[l]);
        if(cmp(tmp)) break; else{ l++; x=tmp; }
      }
      l/=2; r/=2;
    }
    if(l>=r) return N;
    while(l<N){
      S tmp=op(x,V[l*=2]);
      if(!cmp(tmp)){ l++; x=tmp; }
    }
    return l-N;
  }
  template<class Cmp>
  int min_left(int r,Cmp cmp){
    S x=e(); r+=N; int l=N;
    while(l<r && r!=1){
      if(r&1){
        S tmp=op(V[r-1],x);
        if(cmp(tmp)) break; else{ r--; x=tmp; }
      }
      l/=2; r/=2;
    }
    if(l>=r) return 0;
    while(r<=N){
      S tmp=op(V[(r*=2)-1],x);
      if(!cmp(tmp)){ r--; x=tmp; }
    }
    return r-N;
  }
};

const int INF = 2000000000;

using RQS=int;
RQS RMQop(RQS l,RQS r) { return max(l,r); }
RQS RMQe(){ return -1; }
using RMQ=segtree<RQS,RMQop,RMQe>;

int N;
int X[300000];
pair<int,int> I[300000];

struct QueryNode{ int l,x,i; };
vector<QueryNode> queries[300000];
int ans[100000];

int binsearch_GV(int x){
  int l=0, r=N+1;
  while(r-l>1){
    int m=(l+r)/2;
    if(X[I[m-1].second]<x) l=m; else r=m;
  }
  return l;
}

int main(){
  scanf("%d",&N);
  rep(i,N) scanf("%d",X+i);
  rep(i,N) I[i]={X[i],i}; sort(I,I+N);
  rep(i,N) I[I[i].second].first=i;
  RMQ G(N);
  int Q; scanf("%d",&Q);
  rep(i,Q){
    int l,r,x; scanf("%d%d%d",&l,&r,&x); l--;
    queries[r-1].push_back({l,x,i});
  }
  rep(i,N){
    G.set(I[i].first,i);
    for(auto& q:queries[i]){
      int tmp=INF;
      int m = binsearch_GV(q.x);
      int ri = G.max_right(m,[&q](int x)->bool{return q.l<=x;}); if(ri<N) tmp=min(tmp,X[G.get(ri)]-q.x);
      int li = G.min_left(m,[&q](int x)->bool{return q.l<=x;}); if(li>0) tmp=min(tmp,q.x-X[G.get(li-1)]);
      ans[q.i]=tmp;
    }
  }
  rep(i,Q) printf("%d\n",ans[i]);
  return 0;
}
0