D. Rain

千万不要把题目想复杂...一定要学会手推!!!

我们可以通过观察发现以下性质:

$11$.极值一定出现在端点.

$22$.对于出现的每个值我们可以进行差分.

然后可以进行手推发现另外一个性质:

考虑删除一个点对其他点的影响.

假如其他点$id>posid>pos$,那么由公式可以推出该点的$valval$的变化是把$valval$变成了$->val-p[pos]+id-pos->val-p[pos]+id-pos$.

然后根据它要小于等于$mm$进一步推出:.对于所有点都要满足,所以对于最大点要满足.

同理推,那么由公式可以推出该点的$valval$的变化是把$valval$变成了$->val-p[pos]+pos-id->val-p[pos]+pos-id$.

然后根据它要小于等于$mm$进一步推出:.对于所有点都要满足,所以对于最大点要满足.

由此可以维护两个最大值判断以下即可.观察以下可以发现两个下标互换大小更容易满足两个式子,所以可以一起讨论.

还有一个细节问题,其实去掉一个点对于那些值大于m的,可能下标差大于本身的p[pos],这样会使得它们增加,但是增加就更加不符合了,本身为0的时候就不符合,对于那些小于m的,这样做可能会使得它们价值变大,所以在判断的时候要加小于m,return,不然值增加会使得这个去max操作错误.

code:

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;

const int N=2e5+5;
const int M=4;
const int mod=998244353;
const double eps=1e-9;

ll x[N],p[N];
vector<pair<ll,ll>>d;
ll mx=-1e18,MX=-1e18;
ll n,m;

void update(ll val,ll id)
{
	if(val<=m)	return;
	mx=max(mx,val+id-m);
	MX=max(MX,val-id-m);
}

void solve()
{
	d.clear();mx=-1e18,MX=-1e18;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x[i],&p[i]);
		ll st=x[i]-p[i]+1;
		ll ed=x[i]+p[i]+1;
		d.push_back({st,1});
		d.push_back({ed,1}); 
		d.push_back({x[i]+1,-2});
	}
	d.push_back({-2e9,0});
	d.push_back({2e9,0});
	sort(d.begin(),d.end());
	ll D=0,now=0;
	for(int i=1;i<(int)d.size()-1;i++)
	{
		D+=d[i].second;
		if(d[i].first!=d[i+1].first)
		{
			update(now+D,d[i].first);
			update(now+D*(d[i+1].first-d[i].first),d[i+1].first-1);
		}
		now+=D*(d[i+1].first-d[i].first); 
	}
	for(int i=1;i<=n;i++)
	{
		if(mx<=p[i]+x[i]&&MX<=p[i]-x[i])	cout<<1;
		else								cout<<0;
	}
	puts("");
}

int main()
{
	int T=1;
	scanf("%d",&T);
	while(T--)	solve();
	return 0;
}
/*

*/