結果

問題 No.1332 Range Nearest Query
ユーザー 👑 SPD_9X2
提出日時 2021-01-08 23:08:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,320 bytes
コンパイル時間 2,483 ms
コンパイル使用メモリ 208,204 KB
最終ジャッジ日時 2025-01-17 14:15:21
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 RE * 11 TLE * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:84:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   84 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
main.cpp:87:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |         scanf("%d",&tmp);
      |         ~~~~~^~~~~~~~~~~
main.cpp:90:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   90 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
main.cpp:98:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   98 |         scanf("%d%d%d",&l,&r,&a);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

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