結果

問題 No.1332 Range Nearest Query
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2021-01-08 23:11:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,412 bytes
コンパイル時間 3,679 ms
コンパイル使用メモリ 233,392 KB
実行使用メモリ 34,840 KB
最終ジャッジ日時 2024-11-16 15:56:31
合計ジャッジ時間 120,547 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

/*

*/

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#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){
        printf ("%d\n",ans[i]);
    }
}
0