去年就讲的题现在还没调对

金杭东1 · 2025 年5 月 5 日 00:39

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,m,X[N],Y[N],st[N][25];
map<int,int>mp;
int query(int l,int r)
{
	int k=log2(r-l+1);
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>X[i]>>st[i][0];
		mp[X[i]]=i;
	}
	for(int i=1;i<=n;++i)
	for(int j=1;j<=20;++j)
	{
		if(i+(1<<j)>n) continue;
		st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
	cin>>m;
	while(m--)
	{
		int x,y;
		cin>>y>>x;
		if(!mp[x]&&!mp[y])
		{
			cout<<"maybe\n";
			continue;
		}
		int l=1,r=n,idx,idy;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(X[mid]<=x) r=mid;
			else l=mid+1;
		}
		idx=r;
		l=1,r=n;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(X[mid]>=y) r=mid;
			else l=mid+1;
		}
		idy=r;
		if(!mp[y])
		{
			if(query(idy,mp[x]-1)<st[mp[x]][0]) cout<<"maybe\n";
			else cout<<"false\n";
			continue;
		}
		if(!mp[x])
		{
			if(query(mp[y]+1,idx)<st[mp[y]][0]) cout<<"maybe\n";
			else cout<<"false\n";
			continue;
		}
		if(st[mp[x]][0]>st[mp[y]][0])
		{
			cout<<"false\n";
			continue;
		}
		if(query(mp[y]+1,mp[x]-1)>=st[mp[x]][0])
		{
			cout<<"false\n";
			continue;
		}
		bool flag=1;
		for(int i=y;i<=x;++i)
		{
			if(!mp[i])
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			cout<<"maybe\n";
			continue;
		}
		cout<<"true\n";
	}
	return 0;
}

我命由我不由天 · 2025 年5 月 5 日 00:42

~~采用暴力做法~~我看看

金杭东1 · 2025 年5 月 5 日 00:43

暴力法有的TLE50

金杭东1 · 2025 年5 月 5 日 00:43

不过题解说暴力能A

我命由我不由天 · 2025 年5 月 5 日 00:44

@金杭东1 e你给我看暴力吧，太菜了，正解不会

金杭东1 · 2025 年5 月 5 日 00:44

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,m,X[N],Y[N];
unordered_map<int,int>mp;
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>X[i]>>Y[i];
		mp[X[i]]=Y[i];
	}
	cin>>m;
	while(m--)
	{
		int x,y;
		cin>>y>>x;
		if(!mp[x]&&!mp[y])
		{
			cout<<"maybe\n";
			continue;
		}
		if(!mp[y])
		{
			bool flag=1;
			for(int i=1;i<=n;++i)
			{
				if(X[i]<=y) continue;
				if(X[i]>=x) break;
				if(Y[i]>=mp[x])
				{
					flag=0;
					break;
				}
			}
			if(flag) cout<<"maybe\n";
			else cout<<"false\n";
			continue;
		}
		if(!mp[x])
		{
			bool flag=1;
			for(int i=1;i<=n;++i)
			{
				if(X[i]<=y) continue;
				if(X[i]>=x) break;
				if(Y[i]>=mp[y])
				{
					flag=0;
					break;
				}
			}
			if(flag) cout<<"maybe\n";
			else cout<<"false\n";
			continue;
		}
		if(mp[x]>mp[y])
		{
			cout<<"false\n";
			continue;
		}
		bool flag=1;
		for(int i=1;i<=n;++i)
		{
			if(X[i]<=y) continue;
			if(X[i]>=x) break;
			if(Y[i]>=mp[x])
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			cout<<"false\n";
			continue;
		}
		flag=1;
		for(int i=y;i<=x;++i)
		{
			if(!mp[i])
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			cout<<"maybe\n";
			continue;
		}
		cout<<"true\n";
	}
	return 0;
}

我命由我不由天 · 2025 年5 月 5 日 00:44

@金杭东1 我就是用暴力 A 的这道题

金杭东1 · 2025 年5 月 5 日 00:44

暴力要卡常，但是我不会卡

我命由我不由天 · 2025 年5 月 5 日 00:45

@金杭东1 啊，不用卡呀

金杭东1 · 2025 年5 月 5 日 00:45

可能我的暴力常数大吧

金杭东1 · 2025 年5 月 5 日 00:45

umap好像常数挺大的

我命由我不由天 · 2025 年5 月 5 日 00:47

@金杭东1 但是umap 常数肯定比 map 小

金杭东1 · 2025 年5 月 5 日 00:47

map不是常数大，是复杂度大

金杭东1 · 2025 年5 月 5 日 00:49

是不是要先二分，找到比y大的再枚举，我试试

金杭东1 · 2025 年5 月 5 日 00:53

变成T+W了

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,m,X[N],Y[N];
unordered_map<int,int>mp;
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>X[i]>>Y[i];
		mp[X[i]]=Y[i];
	}
	cin>>m;
	while(m--)
	{
		int x,y;
		cin>>y>>x;
		int l=1,r=n,idx;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(X[mid]>=y) r=mid;
			else l=mid+1;
		}
		idx=r+1;
		if(!mp.count(x)&&!mp.count(y))
		{
			cout<<"maybe\n";
			continue;
		}
		if(!mp.count(y))
		{
			bool flag=1;
			for(int i=idx;i<=n;++i)
			{
				if(X[i]>=x) break;
				if(Y[i]>=mp[x])
				{
					flag=0;
					break;
				}
			}
			if(flag) cout<<"maybe\n";
			else cout<<"false\n";
			continue;
		}
		if(!mp.count(x))
		{
			bool flag=1;
			for(int i=idx;i<=n;++i)
			{
				if(X[i]>=x) break;
				if(Y[i]>=mp[y])
				{
					flag=0;
					break;
				}
			}
			if(flag) cout<<"maybe\n";
			else cout<<"false\n";
			continue;
		}
		if(mp[x]>mp[y])
		{
			cout<<"false\n";
			continue;
		}
		bool flag=1;
		for(int i=idx;i<=n;++i)
		{
			if(X[i]>=x) break;
			if(Y[i]>=mp[x])
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			cout<<"false\n";
			continue;
		}
		flag=1;
		for(int i=y;i<=x;++i)
		{
			if(!mp.count(i))
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			cout<<"maybe\n";
			continue;
		}
		cout<<"true\n";
	}
	return 0;
}

连晨皓 · 2025 年5 月 5 日 01:02

这个代码加快读快写试试

连晨皓 · 2025 年5 月 5 日 01:13

循环展开试试

连晨皓 · 2025 年5 月 5 日 01:15

还要二进制优化
实在不行，开个O3优化：
#pragma G++ optimize(3,"Ofast","inline")

金杭东1 · 2025 年5 月 5 日 01:15

666，我还是想写正解

金杭东1 · 2025 年5 月 5 日 01:15

根据一篇警示后人的帖子，我跳到了10分

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,m,X[N],Y[N],st[N][25];
map<int,int>mp;
int query(int l,int r)
{
	int k=log2(r-l+1);
	return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>X[i]>>st[i][0];
		mp[X[i]]=i;
	}
	for(int i=1;i<=n;++i)
	for(int j=1;j<=20;++j)
	{
		if(i+(1<<j)>n) continue;
		st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
	cin>>m;
	while(m--)
	{
		int x,y;
		cin>>y>>x;
		if(!mp[x]&&!mp[y])
		{
			cout<<"maybe\n";
			continue;
		}
		int l=1,r=n,idx,idy;
		while(l<r)
		{
			int mid=(l+r+1)/2;
			if(X[mid]<=x) l=mid;
			else r=mid-1;
		}
		idx=l;
		l=1,r=n;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(X[mid]>=y) r=mid;
			else l=mid+1;
		}
		idy=r;
		if(!mp[y])
		{
			if(mp[x]-1<idy||query(idy,mp[x]-1)<st[mp[x]][0]) cout<<"maybe\n";
			else cout<<"false\n";
			continue;
		}
		if(!mp[x])
		{
			if(idx<mp[y]+1||query(mp[y]+1,idx)<st[mp[y]][0]) cout<<"maybe\n";
			else cout<<"false\n";
			continue;
		}
		if(st[mp[x]][0]>st[mp[y]][0])
		{
			cout<<"false\n";
			continue;
		}
		if(mp[y]+1<=mp[x]-1&&query(mp[y]+1,mp[x]-1)>=st[mp[x]][0])
		{
			cout<<"false\n";
			continue;
		}
		bool flag=1;
		for(int i=y;i<=x;++i)
		{
			if(!mp[i])
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			cout<<"maybe\n";
			continue;
		}
		cout<<"true\n";
	}
	return 0;
}