結果

問題 No.1332 Range Nearest Query
ユーザー 👑 NachiaNachia
提出日時 2021-01-08 23:22:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,605 bytes
コンパイル時間 2,647 ms
コンパイル使用メモリ 219,340 KB
実行使用メモリ 24,872 KB
最終ジャッジ日時 2024-04-28 05:39:59
合計ジャッジ時間 22,282 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
10,752 KB
testcase_01 AC 5 ms
10,752 KB
testcase_02 AC 5 ms
10,624 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 318 ms
23,492 KB
testcase_07 AC 327 ms
23,508 KB
testcase_08 AC 316 ms
23,680 KB
testcase_09 AC 317 ms
23,564 KB
testcase_10 AC 322 ms
23,540 KB
testcase_11 AC 315 ms
23,564 KB
testcase_12 AC 311 ms
23,552 KB
testcase_13 AC 315 ms
23,552 KB
testcase_14 AC 314 ms
23,552 KB
testcase_15 AC 324 ms
23,552 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 224 ms
21,764 KB
testcase_27 AC 272 ms
21,760 KB
testcase_28 AC 106 ms
20,608 KB
testcase_29 AC 108 ms
20,828 KB
testcase_30 AC 106 ms
20,736 KB
testcase_31 AC 107 ms
20,604 KB
testcase_32 AC 106 ms
20,864 KB
testcase_33 AC 111 ms
20,660 KB
testcase_34 AC 112 ms
20,556 KB
testcase_35 AC 106 ms
20,608 KB
testcase_36 AC 109 ms
20,612 KB
testcase_37 AC 111 ms
20,752 KB
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
権限があれば一括ダウンロードができます

ソースコード

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)(),
  class F,
  S(*mapping)(F a, S b),
  F(*composition)(F a, F b),
  F(*id)()
>
struct lazy_segtree {
private:
  struct Node { S v; F r; };
  int N;
  vector<Node> V;

  void spread(int i) {
    V[i].v = mapping(V[i].r, V[i].v);
    if (i < N) {
      V[i * 2].r = composition(V[i].r, V[i * 2].r);
      V[i * 2 + 1].r = composition(V[i].r, V[i * 2 + 1].r);
    }
    V[i].r = id();
  }
public:

  lazy_segtree(int n) {
    N = 1; while (N < n) N *= 2;
    V.assign(N * 2, { e(),id() });
  }
  lazy_segtree(vector<S> A) {
    N = 1; while (N < A.size()) N *= 2;
    V.assign(N * 2, { e(),id() });
    rep(i, A.size()) V[N + i].v = A[i];
    for (int i = N - 1; i >= 1; i--)
      V[i].v = op(V[i * 2].v, V[i * 2 + 1].v);
  }

  void set(int p, S v) {
    p += N;
    for (int d = N; d >= 1; d /= 2) spread(p / d);
    V[p].v = v;
    while (p != 1) {
      p /= 2;
      spread(p * 2); spread(p * 2 + 1);
      V[p].v = op(V[p * 2].v, V[p * 2 + 1].v);
    }
  }
  S get(int p) {
    p += N;
    for (int d = N; d >= 1; d /= 2) spread(p / d);
    return V[p].v;
  }
	S& access(int p){ get(p); return V[p+N].v; }

  void apply(int l, int r, F v, int a = 0, int b = 0, int i = -1) {
    if (i == -1) { a = 0; b = N; i = 1; }
    if (r <= a || b <= l) { spread(i); return; }
    else if (l <= a && b <= r) { V[i].r = composition(v, V[i].r); spread(i); return; }
    spread(i);
    apply(l, r, v, a, (a + b) / 2, i * 2);
    apply(l, r, v, (a + b) / 2, b, i * 2 + 1);
    V[i].v = op(V[i * 2].v, V[i * 2 + 1].v);
  }
};

const int INF=1000000000;

struct S { int a; bool enabled; };
using F = int;
S RmQ_op(S l, S r) { return l; }
S RmQ_e() { return { INF,false }; }
S RmQ_mapping(F f, S a) { if(a.enabled) return {min(f,a.a),true}; else return a; }
F RmQ_composition(F f, F g) { return min(f,g); }
F RmQ_id() { return { INF }; }
using RmQ = lazy_segtree<S, RmQ_op, RmQ_e, F, RmQ_mapping, RmQ_composition, RmQ_id>;
S RMQ_op(S l, S r) { return l; }
S RMQ_e() { return { -INF,false }; }
S RMQ_mapping(F f, S a) { if(a.enabled) return {max(f,a.a),true}; else return a; }
F RMQ_composition(F f, F g) { return max(f,g); }
F RMQ_id() { return { -INF }; }
using RMQ = lazy_segtree<S, RMQ_op, RMQ_e, F, RMQ_mapping, RMQ_composition, RMQ_id>;

struct Query{ int l,r,x; int i,p; };
bool comp_Query_by_x(const Query& l,const Query& r){ return l.x<r.x; }

struct Point{ int x; int i; };
bool comp_Point_by_x(const Point& l,const Point& r){ return l.x<r.x; }

int N,Q;
int X[300000];
Query queries[100000];
int ans[100000];

int binsearch_que(int x){
	int l=0, r=Q+1;
	while(r-l>1){
		int m=(l+r)/2;
		((queries[m-1].x<=x)?l:r) = m;
	}
	return l;
}

struct OnOffQuery{ int p; bool e; };
vector<OnOffQuery> onoff[300001];

int main(){
	scanf("%d",&N);
	rep(i,N) scanf("%d",&X[i]);
	scanf("%d",&Q);
	rep(i,Q){ int l,r,x; scanf("%d%d%d",&l,&r,&x); l--; queries[i]={l,r,x,i,-1}; }

	sort(queries,queries+Q,comp_Query_by_x);
	rep(i,Q){
		auto& q=queries[i];
		onoff[q.l].push_back({i,true});
		onoff[q.r].push_back({i,false});
	}

	RmQ Q1(Q);
	RMQ Q2(Q);
	rep(i,N+1){
		for(auto& q:onoff[i]){
			Q1.access(q.p).enabled=q.e;
			Q2.access(q.p).enabled=q.e;
		}
		if(i==N) break;
		int mid = binsearch_que(X[i]);
		Q1.apply(0,mid,X[i]);
		Q2.apply(mid,Q,X[i]);
	}

	rep(i,Q){
		auto& q=queries[i];
		int tmp=INF;
		tmp=min(tmp,Q1.get(i).a-q.x);
		tmp=min(tmp,q.x-Q2.get(i).a);
		ans[q.i]=tmp;
	}
	rep(i,Q) printf("%d\n",ans[i]);

	return 0;
}
0