結果

問題 No.1332 Range Nearest Query
コンテスト
ユーザー ゆにぽけ
提出日時 2024-01-27 14:33:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,450 bytes
コンパイル時間 1,737 ms
コンパイル使用メモリ 137,576 KB
最終ジャッジ日時 2025-02-19 00:16:42
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <random>
#include <utility>
#include <functional>
using namespace std;
struct Mo{
    int sq;
    vector<int> left,right,order;

    Mo(int N,int Q)
    {
        order.resize(Q);
        sq = max<int>(1,1.0*N/ max<double>(1.0,sqrt(2.0*Q/3.0)));
        iota(order.begin(),order.end(),0);
    }

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

    template<class AL,class AR,class DL,class DR,class REM>
    void run(const AL &addleft,const AR &addright,const DL &delleft,const DR &delright,const REM &rem)
    {
        assert(left.size() == order.size());
        sort(order.begin(),order.end(),[&](int u,int v)
        {
            int ublock = left[u]/sq,vblock = left[v]/sq;
            if(ublock != vblock) return ublock < vblock;

            if(ublock & 1) return right[u] < right[v];
            return right[u] > right[v];
        });

        int nl = 0,nr = 0;
        for(int i:order)
        {
            while(nl > left[i]) addleft(--nl);
            while(nr < right[i]) addright(nr++);
            while(nl < left[i]) delleft(nl++);
            while(nr > right[i]) delright(--nr);

            rem(i);
        }
    }
};
void Main()
{
	int N;
	cin >> N;
	vector<int> X(N);
	for(int i = 0;i < N;i++)
	{
		cin >> X[i];
	}
	int Q;
	cin >> Q;
	Mo mo(N,Q);
	vector<int> x(Q);
	for(int i = 0;i < Q;i++)
	{
		int l,r;
		cin >> l >> r >> x[i];
		mo.insert(--l,r);
	}

	set<int> S;
	vector<int> ans(Q,(int)2e9);
	auto add = [&](int i) -> void
	{
		S.insert(X[i]);
	};
	auto del = [&](int i) -> void
	{
		auto it = S.find(X[i]);
		assert(it != S.end());
		S.erase(it);
	};
	auto rem = [&](int i) -> void
	{
		auto it = S.lower_bound(x[i]);
		if(it != S.end())
		{
			ans[i] = min(ans[i],*it - x[i]);
		}
		if(it != S.begin())
		{
			it--;
			ans[i] = min(ans[i],x[i] - *it);
		}
	};
	mo.run(add,add,del,del,rem);
	for(int i = 0;i < Q;i++)
	{
		cout << ans[i] << "\n";
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt = 1;
	/* cin >> tt; */
	while(tt--) Main();
}
0