救 救 孩 子
查看原帖
救 救 孩 子
182260
zero2005楼主2020/11/17 09:01
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maybe cout<<"maybe"<<'\n';
#define true 	cout<<"true"<<'\n';
#define false cout<<"false"<<'\n';
int n,m;
struct rea
{
	int nian;int w;
	int val;
}a[1000001];
struct res
{
	int val;int w;
}b[1000001];
map<int,int>ver;
map<int ,int >edge;
bool cmp(rea a,rea b)
{
	return a.nian <b.nian;
}
bool cmp1(res a,res b)
{
	return a.val<b.val ;
}
struct rec
{
	int l,r,max,min;
}tree[5000001];
map<int,int>q;
void build(int p,int l,int r)
{
	tree[p].l =l;
	tree[p].r=r;
	if(l==r)
	{
		tree[p].max=edge[l];
		tree[p].min=edge[l];
	//	cout<<tree[p].max<<endl;
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].max=max(tree[p*2].max,tree[p*2+1].max);
	tree[p].min=min(tree[p*2].min,tree[p*2+1].min);
}
int ask(int p,int l,int r)
{
	if(tree[p].l >=l&&tree[p].r<=r)
	{
		return tree[p].max ;
	}
	int val=-9999999999;
	int mid=(tree[p].l+tree[p].r )>>1;
	if(l<=mid)
	{
		val=max(val,ask(p*2,l,r));
	}
	if(r>mid)
	{
		val=max(val,ask(p*2+1,l,r));
	}
	return val;
}
int ask2(int p,int l,int r)
{
	if(tree[p].l >=l&&tree[p].r<=r)
	{
		return tree[p].min;
	}
	int val=9999999999;
	int mid=(tree[p].l+tree[p].r )>>1;
	if(l<=mid)
	{
		val=min(val,ask2(p*2,l,r));
	}
	if(r>mid)
	{
		val=min(val,ask2(p*2+1,l,r));
	}
	return val;
}
int x,y,z;
signed main()
{
	cin>>n;
	int l=99999999;
	int r=-999999999;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].nian;
		a[i].w=i;
		cin>>a[i].val;
		l=min(l,a[i].nian );
		r=max(r,a[i].nian );
	}
	sort(a+1,a+n+1,cmp);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i].nian !=a[i-1].nian)cnt++;
		if(a[i].nian >a[i-1].nian +1&&i!=1)
		{
		   ver[a[i-1].nian +1]=cnt;
		    edge[cnt]=-999999999999;
		   cnt++;
		}
      ver[a[i].nian ]=cnt;
      edge[cnt]=a[a[i].w ].val ;
	}
	
//	cout<<l<<' '<<r<<endl;
//	cout<<tot<<endl;
     build(1,1,cnt);
     cin>>m;
     for(int i=1;i<=m;i++)
     {
     	cin>>x>>y;
     	int xx=ver[x];
     	int yy=ver[y];
     	if(x<l||x>r||edge[ver[x]]==-999999999999)
     	{
     		if(y<l||y>r||edge[yy]==-999999999999)
     		{
     			maybe
     			continue;
     		}
     		if(ver[yy]&&ver[yy]!=-999999999999)
     		{
     			if(x>=l&&y-x>1)
     			{
     				int kk=ask(1,xx+1,yy-1);
     				if(edge[yy]>kk)
     				{
     					maybe;
     					continue;
     				}
     				else
     				{
     					false;
     					continue;
     				}
     			}
     		}
     	}if(y-x<1)
     	{
     		false;
     		continue;
     	}
     	if(y<l||y>r||edge[yy]==-999999999999)
     	{
     		if(x>=l&&x<r&&edge[xx]!=-999999999999)
     		{
     			if(y>r)
     			{
     				int kk=ask(1,xx+1,r);
     				if(kk>edge[xx])
     				{
     					false;
     					continue;
     				}
     				else
     				{
     					maybe;
     					continue;
     				}
     				
     			}
     			if(y<=r)
     			{
     				int kk=ask(1,xx+1,yy-1);
     				
     					if(kk>edge[xx])
     				{
     					false;
     					continue;
     				}
     				else
     				{
     					maybe;
     					continue;
     				}
     				
     			}
     		}
     	}
     	
     	int kk=ask(1,xx+1,yy-1);
     	int tt=ask2(1,xx+1,yy);
     	if(edge[yy]<=kk)
     	{
     		false;
     		continue;
     	}
     	if(edge[yy]>kk&&tt!=-999999999999)
     	{
     		true;
     		continue;
     	}
     	if(edge[yy]>kk&&tt==-999999999999)
     	{
     		maybe;
     		continue;
     	}
     }
	return 0;

}
2020/11/17 09:01
加载中...