求助!!!
查看原帖
求助!!!
102709
zjy1412楼主2020/8/20 15:39

我去poj下的数据,测出来一摸一样,结果luogu和poj都全wa,请问是什么玄学错误。。。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
#define re register
#define debug printf("zjy\n")
#define lp (p<<1)
#define rp (p<<1|1)
inline int read(){
	int a=0,b=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')b=-1;c=getchar();}
	while(isdigit(c)){a=a*10+c-'0';c=getchar();}
	return a*b;
}
const int N=2e5+50,M=2e6+50,zxt=1e9;
int n,m,q,b[N],rr[N],tot,maxn[M],dat[M],inf=2147483647;
void build(int p,int l,int r){
	if(l==r){
		maxn[p]=rr[l];
		if(rr[l]<=zxt)dat[p]=rr[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lp,l,mid);
	build(rp,mid+1,r);
	maxn[p]=max(maxn[lp],maxn[rp]);
	dat[p]=max(dat[lp],dat[rp]);
}
int ask(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R){
		return maxn[p];
	}
	int mid=(l+r)>>1,val=0;
	if(L<=mid)val=max(val,ask(lp,l,mid,L,R));
	if(R>mid)val=max(val,ask(rp,mid+1,r,L,R));
	return val;
}
int find(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R){
		return dat[p];
	}
	int mid=(l+r)>>1,val=0;
	if(L<=mid)val=max(val,find(lp,l,mid,L,R));
	if(R>mid)val=max(val,find(rp,mid+1,r,L,R));
	return val;
}
signed main(){
	n=read();
	for(re int i=1;i<=n;i++){
		b[++tot]=read();rr[tot]=read();
		if(b[tot]!=b[tot-1]+1){
			b[++tot]=b[tot-1];rr[tot]=rr[tot-1];
			b[tot-1]=b[tot]-1;rr[tot-1]=inf;
		}
	}
	b[++tot]=2147483648;rr[tot]=inf;
//	for(re int i=1;i<=tot;i++)printf("!!%lld %lld\n",b[i],rr[i]);
	build(1,1,tot);
	m=read();int u,v,k;bool flag;
	for(re int i=1;i<=m;i++){
		flag=0;
		u=read();v=read();
		if(u==v){
			printf("false\n");
			continue;
		}
		u=lower_bound(b+1,b+tot+1,u)-b;
		v=lower_bound(b+1,b+tot+1,v)-b;
		if(rr[u]>zxt&&rr[v]>zxt){
			printf("maybe\n");
			continue;
		}
		if(ask(1,1,tot,u,v)>zxt)flag=1;
		if(rr[u]<rr[v]&&rr[u]<=zxt&&rr[v]<=zxt){
			printf("false\n");
			continue;
		}
		if(u+1==v){
			if(flag)printf("maybe\n");
			else printf("true\n");
		}
		else if(find(1,1,tot,u+1,v-1)<min(rr[v],rr[u])){
			if(flag)printf("maybe\n");
			else printf("true\n");
		}
		else printf("false\n");
	}
	return 0;
}
2020/8/20 15:39
加载中...