线段树50pts求调
查看原帖
线段树50pts求调
1285033
liyoulin楼主2025/2/8 13:43
#include<bits/stdc++.h>
using namespace std;
int d[200004],n,m,year[50001],rain[50001],x,y,a,b;
bool f;
void build(int s,int t,int p){
	if(s==t){
		d[p]=rain[s];
		return;
	}
	int m=s+((t-s)>>1);
	build(s,m,2*p);
	build(m+1,t,2*p+1);
	d[p]=max(d[2*p],d[2*p+1]);
}
int getmax(int l,int r,int s,int t,int p){
	if(s>=l&&t<=r){
		return d[p];
	}
	int m=s+((t-s)>>1),sum=-1000000000;
	if(l<=m) sum=max(sum,getmax(l,r,s,m,2*p));
	if(r>m) sum=max(sum,getmax(l,r,m+1,t,2*p+1));
	return sum;
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>year[i]>>rain[i];
	}
	build(1,n,1);
	cin>>m;
	while(m--){
		f=0;
		cin>>y>>x;
		bool f1=0,f2=0,f3=0;
		a=y,b=x;
		y=lower_bound(year+1,year+n+1,y)-year;
		if(year[y]!=a) f=1;
		x=upper_bound(year+1,year+n+1,x)-year-1;
		if(year[x]!=b){
			if(f){
				f1=1;
			}
			else{
				f=1;
				f3=1;
			}
		}
		else if(f){
			f2=1;
		}
		if(year[x]-year[y]!=x-y) f=1;
		if(f1||(getmax(y+1,x-1,1,n,1)<rain[f3?y:x]&&rain[f2?y:x]<=rain[y])){
			if(f){
				cout<<"maybe\n";
			}
			else cout<<"true\n";
		}
		else{
			cout<<"false\n";
		}
	}
	return 0;
}

WA #1,#3,#4,#5,#6

2025/2/8 13:43
加载中...