样例能过,求调
查看原帖
样例能过,求调
796667
ZY_jiang楼主2024/4/19 19:28
#include<bits/stdc++.h>
#define ll long long
#define ls u<<1
#define rs u<<1|1
using namespace std;
const int N =50005;
struct tree{
	ll l,r,pos,lazy,minn;
}tr[N*4];
struct node{
	ll id,pos;
}q[N];
map <ll,ll> mp;
ll n,m,k,c,ans,fl=0,f2;
void pushup(ll u){
	tr[u].pos=max(tr[ls].pos,tr[rs].pos);
	if(tr[ls].minn==-1||tr[rs].minn==-1) tr[u].minn=-1;
	return ;
}
void build(ll u,ll l,ll r){
	tr[u].l=l;
	tr[u].r=r;
//	tr[u].minn=0;
	if(l==r){
		tr[u].pos=q[l].pos;
		if(q[l].pos==-1) tr[u].minn=-1;
		else tr[u].minn=0;
		return ;
	}
	ll mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(u);
	return ;
}
void found(ll u,ll l,ll r,ll maxn){
	if(l<=tr[u].l&&tr[u].r<=r){
		if(tr[u].pos<=maxn) fl=0;
//		if(tr[u].minn==-1) fl=2;
		return ;
	}
	ll mid=(tr[u].l+tr[u].r)>> 1;
	if(l<=mid) found(ls,l,r,maxn);
	if(r>mid) found(rs,l,r,maxn);
}
int main(){
	for(int i=1;i<=N;i++){
		q[i].pos=-1;
	}
	cin>>n;
	
	for(int i=1;i<=n;i++){
		cin>>q[i].id>>q[i].pos;
		mp[q[i].id]=i;
	}
	build(1,1,n);
	cin>>m;
	/*
	fl 0 true
	fl 1 false
	fl 2 maybe
	*/
	for(int i=1;i<=m;i++){
		ll x,y,s;
		fl=1;
		cin>>x>>y;
		if(x>=y){
			cout<<"false"<<endl;
			continue;
		}
		ll sum=q[mp[x]].pos;
//		cout<<sum<<endl;
		found(1,mp[x],mp[y],sum);
		if(fl==1) cout<<"false"<<endl;
		else if(mp[x]-mp[y]!=x-y) cout<<"maybe"<<endl;
		else if(fl==0) cout<<"true"<<endl;
	
	}
	return 0;
} 
2024/4/19 19:28
加载中...