0分 求助 感觉和题解的代码没什么区别
查看原帖
0分 求助 感觉和题解的代码没什么区别
173056
_Veritas楼主2021/2/1 14:06

RT

#include<iostream>
#include<cstdio>
using namespace std;
inline int read(){
	int x=0;char c=getchar();bool f=false;
	while((c<'0'||c>'9')&&c!='-') c=getchar();
	if(c=='-') f=true,c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
int n,m,st[50004][20],sum[50004],X,Y,x,y,z,logn[50004]={-1},year[50004];
inline int find(int x){
	int l=1,r=n,ans=n;
	while(l<=r)
		if(year[(l+r)>>1]>=x)
			r=(ans=((l+r)>>1))-1;
		else
			l=((l+r)>>1)+1;
	return ans;
}
inline int query(int l,int r){return r<l?-2147483647:max(st[l][logn[r-l+1]],st[r+1-(1<<logn[r-l+1])][logn[r-l+1]]);}
int main(){
	n=read();
	for(int i=1;i<=n;++i)
		year[i]=read(),st[i][0]=read(),sum[i]=sum[i-1]+(year[i]!=year[i-1]+1),logn[i]=logn[i/2]+1;
	for(int j=1;j<=logn[n];++j)
		for(int i=1;i+(1<<j)-1<=n;++i)
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
	m=read();
	while(m--){
		y=find(Y=read());x=find(X=read());
		if(Y>=X){puts("false");continue;}
		if(year[y]==Y)
			if(year[x]==X){
				if(st[x][0]>st[y][0]){puts("false");continue;}
				z=query(y+1,x-1);
				if(st[x][0]<=z){puts("false");continue;}
				if(sum[x]!=sum[y]){puts("maybe");continue;}
				puts("true");
			}
			else{
				z=query(y+1,x-1);
				if(z<st[y][0]){puts("maybe");continue;}
				puts("false");
			}
		else
			if(year[x]==X){
				z=query(y,x-1);
				if(st[x][0]<=z){puts("false");continue;}
				puts("maybe");
			}
			else
				puts("maybe");
	}
	return 0;
}
2021/2/1 14:06
加载中...