結果

問題 No.1332 Range Nearest Query
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2021-01-08 23:08:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,320 bytes
コンパイル時間 2,293 ms
コンパイル使用メモリ 216,448 KB
実行使用メモリ 24,652 KB
最終ジャッジ日時 2024-04-28 04:57:02
合計ジャッジ時間 8,337 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,752 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*

*/

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
#define rrep(i,n,m) for(int (i)=(n);(i)>(m);(i)--)
using ll = long long;

int N,Q;
set<int> S;
vector<int> X(0);

struct Mo
{
  vector< int > left, right, order;
  vector< bool > v;
  int width;
  int nl, nr, ptr;

  Mo(int n) : width((int) sqrt(n)), nl(0), nr(0), ptr(0), v(n) {}

  void insert(int l, int r) /* [l, r) */
  {
    left.push_back(l);
    right.push_back(r);
  }

  /* ソート */
  void build()
  {
    order.resize(left.size());
    iota(begin(order), end(order), 0);
    sort(begin(order), end(order), [&](int a, int b)
    {
      if(left[a] / width != left[b] / width) return left[a] < left[b];
      return right[a] < right[b];
    });
  }

  /* クエリを 1 つぶんすすめて, クエリのidを返す */
  int process()
  {
    if(ptr == order.size()) return (-1);
    const auto id = order[ptr];
    while(nl > left[id]) distribute(--nl);
    while(nr < right[id]) distribute(nr++);
    while(nl < left[id]) distribute(nl++);
    while(nr > right[id]) distribute(--nr);
    return (order[ptr++]);
  }

  inline void distribute(int idx)
  {
    v[idx].flip();
    if(v[idx]) add(idx);
    else del(idx);
  }

  void add(int idx);

  void del(int idx);
};

void Mo::add(int idx)
{
  S.insert(X[idx]);
}

void Mo::del(int idx)
{
  S.erase(X[idx]);
}

int iabs(int d){
    if (d < 0) return -d;
    else return d;
}

int main(){

    scanf("%d",&N);
    int tmp;
    rep(i,0,N){
        scanf("%d",&tmp);
        X.push_back(tmp);
    }
    scanf("%d",&Q);

    int ind;
    vector<int> ans(Q,INT_MAX);
    vector<int> alis(N);
    Mo mo(N);
    rep(loop,0,Q){
        int l,r,a;
        scanf("%d%d%d",&l,&r,&a);
        mo.insert(l-1,r);
        alis[loop] = a;
    }

    //cout << ans[2] << endl;
    mo.build();
    rep(loop,0,Q){
        ind = mo.process();
        auto it = S.lower_bound(alis[ind]);
        //cout << ind << " " << alis[ind]  << " " << *it << endl;
        if (it != S.end()) ans[ind] = min(ans[ind] , iabs(alis[ind]-*it) );
        if (it != S.begin()) it--;
        //cout << ind << " " << alis[ind]  << " " << *it << endl;
        if (it != S.end()) ans[ind] = min(ans[ind] , iabs(alis[ind]-*it) );
    }

    rep(i,0,Q){
        cout << ans[i] << '\n';
    }
}
0