萌新求助!50分WA 救救孩子!(P2471降雨量)
查看原帖
萌新求助!50分WA 救救孩子!(P2471降雨量)
153139
风羽跃楼主2021/6/28 19:15
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

#define INF 0x7fffffff

#define maxn 50010

using namespace std;

inline int max(int a,int b)
{
	return a>b?a:b;
}

int n,m;
int ye[maxn],k[maxn];

struct Tree{
	int l,r,mx;
	#define l(p) tree[p].l
	#define r(p) tree[p].r
	#define mx(p) tree[p].mx
//	#define cmx(p) tree[p].cmx
	#define ls p*2
	#define rs p*2+1
}tree[maxn*4];

inline void build(int p,int l,int r)
{
	l(p)=l,r(p)=r;
	if(l==r){
		mx(p)=k[l];
		return ;
	}
	int mid=l(p)+r(p)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	mx(p)=max(mx(ls),mx(rs));
}

inline int ask(int p,int l,int r)
{
	if(l<=l(p)&&r>=r(p)) return mx(p);
	int mid=l(p)+r(p)>>1;
	int val=-INF;
	if(l<=mid) val=max(val,ask(ls,l,r));
	if(r>mid) val=max(val,ask(rs,l,r));
	return val;
}

//inline int lower(int x)
//{
//	int l=1,r=n;
//	while(l<r){
//		int mid=l+r>>1;
//		if(ye[mid]>=x) r=mid;
//		else l=mid+1;
//	}
//	return l;
//}

//using namespace std;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ye[i]>>k[i];
	}
	build(1,1,n);
	cin>>m;
	while(m--){
		int y,x;
		cin>>y>>x;
		if(x<=y){
			cout<<"false"<<endl;
			continue;
		}
		int a=lower_bound(ye+1,ye+n+1,y)-ye,b=lower_bound(ye+1,ye+n+1,x)-ye;
		if(ye[a]!=y&&ye[b]!=x){
			cout<<"maybe"<<endl;
		}
		if(ye[a]==y&&ye[b]!=x){
			if(b==a+1) cout<<"maybe"<<endl;
			else{
				int s=ask(1,a+1,b-1);
				if(s>=k[a]) cout<<"false"<<endl;
				else cout<<"maybe"<<endl;
			}
		}
		if(ye[a]!=y&&ye[b]==x){
			if(b==a+1) cout<<"maybe"<<endl;
			else{
				int s=ask(1,a+1,b-1);
				if(s>=k[b]) cout<<"false"<<endl;
				else cout<<"maybe"<<endl;
			}
		}
		if(ye[a]==y&&ye[b]==x){
			if(k[b]>k[a]) cout<<"false"<<endl;
			else{
				if(b==a+1){
					if(x==y+1) cout<<"true"<<endl;
					else cout<<"maybe"<<endl;
				}
				else{
					int s=ask(1,a+1,b-1);
					if(s>=k[b]) cout<<"false"<<endl;
					else{
						if(x-y!=b-a) cout<<"maybe"<<endl;
						else cout<<"true"<<endl;
					}
				}
			}
		}
	}
	return 0;
}
2021/6/28 19:15
加载中...