結果

問題 No.1332 Range Nearest Query
ユーザー 👑 Nachia
提出日時 2021-01-08 23:22:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,605 bytes
コンパイル時間 2,825 ms
コンパイル使用メモリ 210,696 KB
最終ジャッジ日時 2025-01-17 14:40:57
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 WA * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:113:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  113 |         scanf("%d",&N);
      |         ~~~~~^~~~~~~~~
main.cpp:114:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  114 |         rep(i,N) scanf("%d",&X[i]);
      |                  ~~~~~^~~~~~~~~~~~
main.cpp:115:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  115 |         scanf("%d",&Q);
      |         ~~~~~^~~~~~~~~
main.cpp:116:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |         rep(i,Q){ int l,r,x; scanf("%d%d%d",&l,&r,&x); l--; queries[i]={l,r,x,i,-1}; }
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

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