莫名其妙的问题:ST
查看原帖
莫名其妙的问题:ST
648660
Name1楼主2022/5/22 15:33

总是50分,求大佬帮忙看看

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,m;
ll y[N],st[N][20];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
int find(int x)
{
	int l=1,r=n;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(y[mid]==x)return mid;
		else if(y[mid]<x)l=mid+1;
		else r=mid-1;
	}
	return l;
}
int getmax(int l,int r)
{
	int len=log2(r-l+1);
	return max(st[l][len],st[r-(1<<len)+1][len]);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)y[i]=read(),st[i][0]=read();
	for(int l=1;l<=log2(n);l++)
		for(int i=1;(i+(1<<l)-1)<=n;i++)
			st[i][l]=max(st[i][l-1],st[i+(1<<(l-1))][l-1]);
	y[n+1]=1<<20,m=read();
	while(m--)
	{
		ll Y=read(),X=read();
		if(Y>=X){puts("false");continue;}
		//int u=find(Y),v=find(X);
		int u=lower_bound(y+1,y+n+1,Y)-y;
        int v=lower_bound(y+1,y+n+1,X)-y;
		if(y[u]==Y&&y[v]==X)
		{
			if(st[u][0]<st[v][0])puts("false");
			else if(u==v-1)
			{
				if(X==Y+1)puts("true");
				else puts("maybe");
			}
			else 
			{
				ll ans=getmax(u+1,v-1);
				
				if(st[v][0]<=ans)puts("false");
				else
				{
					if(X-Y==v-u) puts("true");
					else puts("maybe");
				}
			}
		}
		else if(y[u]!=Y&&y[v]==X)
		{
			if(u==v)puts("maybe");
			else 
			{
				ll ans=getmax(u,v-1);
				if(ans>=st[v][0])puts("false");
				else puts("maybe");
			}
		}
		else if(y[u]==Y&&y[v]!=X)
		{
			if(v=u+1)puts("maybe");
			else 
			{
				ll ans=getmax(u+1,v-1);
				if(st[u][0]<=ans)puts("false");
				else puts("maybe");
			}
		}
		else puts("maybe");
	}
	return 0;
}
2022/5/22 15:33
加载中...