求助求助,60分
查看原帖
求助求助,60分
363495
我爱杨帆楼主2020/10/14 11:07
#include<bits/stdc++.h>
using namespace std;
struct tree
{
	int l,r,dat;
}t[4000000];
#define l(p) t[p].l
#define r(p) t[p].r
#define mul(p) t[p].mul
#define dat(p) t[p].dat
#define l1(p) t1[p].l1
#define r1(p) t1[p].r1
#define mul1(p) t1[p].mul1
#define dat1(p) t1[p].dat1
int rain[500000],y[500000];
int read()
{
	char c;
	int f=1,r=0;
	c=getchar();
	while(c!='-'&&(c<'0'||c>'9'))
	c=getchar();
	if(c=='-')
	{
	f=-1;
    c=getchar();
	}
	while(c>='0'&&c<='9')
	{
	r=r*10+c-'0';
    c=getchar();
	}
	return r*f;
}	
void build(int p,int l,int r)
{   
    l(p)=l,r(p)=r;
  	if(l==r)
  	{
  	 dat(p)=rain[l];
	 return;	
	}
	int mid=(l+r)/2;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	dat(p)=max(dat(2*p),dat(2*p+1)); 
}
int ask_dat(int p,int l,int r)
{
 if(l<=l(p)&&r>=r(p))
 return dat(p);
 int mid=(l(p)+r(p))/2;
 int ans=0;
 if(l<=mid)
 ans=max(ask_dat(2*p,l,r),ans);
 if(r>mid)
 ans=max(ans,ask_dat(2*p+1,l,r));
 return ans;	
} 	      
int main()
{
	int n=read();
	for(int i=1;i<=n;i++)
	{
		y[i]=read();
		rain[i]=read();
	}
	build(1,1,n);
	int m=read();
	for(int i=1;i<=m;i++)
	{	int p1,p2,f1=0,f2=0;
		int xx=read(),yy=read();
		p1=lower_bound(y+1,y+1+n,xx)-y;
		p2=lower_bound(y+1,y+1+n,yy)-y;
		if(y[p1]==xx)
		f1=1;
		if(y[p2]==yy)
		f2=1;
		if(!f1&&!f2)
		{
			cout<<"maybe"<<endl;
			continue;
		}
		if(f1&&f2)
		{
			if(rain[p2]>rain[p1])
			{
				cout<<"false"<<endl;
				continue;
			}
			if(yy==xx+1)
			{
				cout<<"true"<<endl;
				continue;
			}
			if(p2==p1+1)
			{
				cout<<"maybe"<<endl;
				continue;
			}
			if(ask_dat(1,p1+1,p2-1)>=rain[p2])
			{
				cout<<"false"<<endl;
				continue;
			}
			if(p2-p1==yy-xx)
			{
				cout<<"true"<<endl;
				continue;
			}
			cout<<"maybe"<<endl;
			continue;
		}
		if(!f1&&f2)
		{
			if(p1+1==p2)
			{
				cout<<"maybe"<<endl;
				continue;
			}
			if(ask_dat(1,p1,p2-1)>=rain[p2])
			{
				cout<<"false"<<endl;
				continue;
			}
			cout<<"maybe"<<endl;
			continue;
		}
		if(f1&&!f2)
		{
			if(p1+1==p2)
			{
				cout<<"maybe"<<endl;
				continue;
			}
			if(ask_dat(1,p1+1,p2-1)>=rain[p1])
			{
				cout<<"false"<<endl;
				continue;
			}
			cout<<"maybe"<<endl;
			continue;
		}
	}
}
2020/10/14 11:07
加载中...