比赛 20110311 评测结果 AAAAWWAAAW
题目名称 图的平方 最终得分 70
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-03-11 20:14:23
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=100005,MAXM=5000;

vector<int>v;
vector<pair<int,int> >adj[MAXM];
vector<int> adj2[MAXM];
vector<int> adj3[MAXM];
vector<int> adj4[MAXM];
int hash[MAXN];
vector<int> rhash;
int u1[MAXM],u2[MAXM],v1[MAXM],v2[MAXM];
int A[MAXM][MAXM];
int N,M;

int main()
{
	freopen("ljb.in","r",stdin);
	freopen("ljb.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=0;i<M;i++)
	{
		scanf("%d%d%d%d",u1+i,u2+i,v1+i,v2+i);
		v.push_back(u1[i]);
		v.push_back(u2[i]);
		v.push_back(v1[i]);
		v.push_back(v2[i]);
	}
	sort(v.begin(),v.end());
	int tot=0;
	for(int i=0,j=0;i<v.size();i++,tot=j)
		if (i==0 || v[i]!=v[i-1])
		{
			rhash.push_back(v[i]);
			hash[v[i]]=j++;
		}
	for(int i=0;i<M;i++)
		for(int j=hash[u1[i]];j<=hash[u2[i]];j++)
			adj[j].push_back(make_pair(hash[v1[i]],hash[v2[i]]));
	for(int i=0;i<tot;i++)
	{
		sort(adj[i].begin(),adj[i].end());
		int s=-1;
		for(int j=0;j<adj[i].size();j++)
		{
			for(int k=max(adj[i][j].first,s);k<=adj[i][j].second;k++)
				A[i][k]=1;
			if (adj[i][j].second>s)
				s=adj[i][j].second;
		}
		for(int j=0;j<tot;j++)
			if (A[i][j]==1)
				adj2[i].push_back(j);
	}
	for(int i=0;i<tot;i++)
	{
		for(int j=0;j<adj2[i].size();j++)
		{
			int v=adj2[i][j];
			for(int k=0;k<adj2[v].size();k++)
				adj3[i].push_back(adj2[v][k]);
		}
		sort(adj3[i].begin(),adj3[i].end());
		for(int j=0;j<adj3[i].size();j++)
			if (j==0 || adj3[i][j]!=adj3[i][j-1])
				adj4[i].push_back(adj3[i][j]);
	}
	scanf("%d",&N);
	while(N--)
	{
		int x1,x2,y1,y2;
		scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
		x1=hash[*(upper_bound(rhash.begin(),rhash.end(),x1)-1)];
		x2=hash[*(lower_bound(rhash.begin(),rhash.end(),x2))];
		y1=hash[*(upper_bound(rhash.begin(),rhash.end(),y1)-1)];
		y2=hash[*(lower_bound(rhash.begin(),rhash.end(),y2))];
		int i;
		for(i=x1;i<=x2;i++)
		{
			vector<int>::iterator it1,it2;
			it1=lower_bound(adj4[i].begin(),adj4[i].end(),y1);
			it2=lower_bound(adj4[i].begin(),adj4[i].end(),y2);
			if (it2-it1!=y2-y1)
			{
				printf("No\n");
				break;
			}
		}
		if (i==x2+1)
			printf("Yes\n");
	}
	return 0;
}