有T有WA,怎么办
查看原帖
有T有WA,怎么办
291604
王茗仟楼主2023/2/16 09:03
#define double long double
#define int128 __int128
#define int long long
#define re register
#define in inline
#define Pi pair<int,int>
#define vi vector<int>
#define max(a,b)  ((a)>(b)?a:b)
#define min(a,b)  ((a)<(b)?a:b)
#define ls x<<1
#define rs x<<1|1

#define mid ((l+r)>>1)
#define dx x+xx[i]
#define dy y+yy[i]
#define debug cout<<"wuyu"<<endl;
using namespace std;
const int INF=0x3f3f3f3f3f;
const int N=2e5+19;
const int M=1e6+10;
const int mod=998244353;
const double eps=1e-5;
in int read(){	re int x=0,f=0;re char c=getchar();	while(!isdigit(c)) f|=(c=='-'),c=getchar();	while(isdigit(c))  x=(x<<3)+(x<<1)+c-'0',c=getchar();	return f?-x:x;}
in void write(re int x){	if(x<0) putchar('-'),x=-x;	if(x>9) write(x/10);	putchar(x%10+'0');}




int n,m;
int t[N*3];
int year[N],rain[N];

void update(int x,int l,int r,int L,int k){
	if(l==r){
		t[x]=k;
		return ;
	}
	if(L<=mid) update(ls,l,mid,L,k);
	else update(rs,mid+1,r,L,k);
	t[x]=max(t[ls],t[rs]);
}

int query(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return t[x];
	}
	int ans=-1e9;
	if(L<=mid) ans=max(ans,query(ls,l,mid,L,R));
	if(R>mid)  ans=max(ans,query(rs,mid+1,r,L,R));
	return ans;
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		year[i]=read();rain[i]=read();
		update(1,1,n,i,rain[i]);
	}
	m=read();
	int p1,p2,f1,f2,x,y;
	for(int i=1;i<=m;i++){
		y=read();x=read();
		p1=lower_bound(year+1,year+1+n,y)-year;
		p2=lower_bound(year+1,year+1+n,x)-year;
		f1=(p1==n+1||year[p1]!=y) ?0:1;
		f2=(p2==n+1||year[p2]!=x)?0:1;
		if(y>x){
			cout<<"false"<<endl;
			continue;
		}
		if(!f1&&!f2){
			cout<<"maybe"<<endl;
			continue;
		}
		if(f1&&f2){
			if(rain[p1]<rain[p2]){
				cout<<"false"<<endl;
				continue;
			}
			if(y+1==x){
				cout<<"true"<<endl;
				continue;
			}
			if(p1+1==p2){
				cout<<"maybe"<<endl;
				continue;
			}
			int maxn=query(1,1,n,p1+1,p2-1);
			if(maxn>=rain[p1]){
				cout<<"false"<<endl;
				continue;
			}
			if(p2-p1==x-y){
				cout<<"true"<<endl;
				continue;
			}
			else{
				cout<<"maybe"<<endl;
				continue;
			}
		}
		else if(f1){
			if(p1+1==p2){
				cout<<"maybe"<<endl;
				continue;
			}
			int maxn=query(1,1,n,p1+1,p2-1);
			if(maxn>=rain[p1]){
				cout<<"false"<<endl;
				continue;
			}
			else{
				cout<<"maybe"<<endl;
				continue;
			}
		}
		else if(f2){
			if(p1==p2){
				cout<<"maybe"<<endl;
				continue;
			}
			int maxn=query(1,1,n,p1,p2-1);
			if(maxn>=rain[p2]){
				cout<<"false"<<endl;
				continue;
			}
			else{
				cout<<"maybe"<<endl;
				continue;
			}
		}
	}
	return 0;
}







2023/2/16 09:03
加载中...