比赛 20160909 评测结果 AAWTAWT
题目名称 基本的图问题 最终得分 42
用户昵称 悟理 运行时间 2.136 s
代码语言 C++ 内存使用 1.05 MiB
提交时间 2016-09-09 21:50:52
显示代码纯文本
#include <fstream>

using namespace std;

const int MAX_VALUE = 100001;
int Data[MAX_VALUE];
int FatherOf[MAX_VALUE];
//int Min[MAX_VALUE];
//int Max[MAX_VALUE];

inline int GetInt(FILE *fin)
{
	int num = 0,flag = 0;
	char ch;
	ch = fgetc(fin);
	while(' ' == ch || '\n' == ch)
		ch = fgetc(fin);
	if ('-' == ch)
	{
		flag = 1;
		ch = fgetc(fin);
	}
	while('0' <= ch && ch <= '9')
	{
		num = (num << 3) + (num << 1) + ch - '0';
		ch = fgetc(fin);
	}
	if (flag)
		return -num;
	else
		return num;
}

inline int FindFather(int x)
{
	if (FatherOf[x] != x)
		FatherOf[x] = FindFather(FatherOf[x]);
	return FatherOf[x];
}

inline void Merge(int x,int y)
{
	FatherOf[FindFather(y)] = FindFather(x);
}

int Main()
{
	FILE *fin = fopen("basicgraph.in","r");
	FILE *fout = fopen("basicgraph.out","w");
	
	int DataSize = GetInt(fin);
	//int p_max = 0,p_min = 0;
	Data[1] = GetInt(fin);
	FatherOf[1] = 1;
	Data[0] = 0;
	for (int i = 2;i <= DataSize;++i)
	{
		Data[i] = GetInt(fin);
		/*if (Data[i - 2] > Data[i - 1] && Data[i - 1] < Data[i])
		{
			Min[p_min] = i - 1;
			++p_min;
		}
		else if (Data[i - 2] < Data[i - 1] && Data[i - 1] > Data[i])
		{
			Max[p_max] = i - 1;
			++p_max;
		}*/
		FatherOf[i] = i;
	}
	
	int DataSize_L = GetInt(fin);
	int left,right,max = 0,min = MAX_VALUE;
	for (int i = 1;i <= DataSize_L;++i)
	{
		left = GetInt(fin);
		right = GetInt(fin);
		/*for (int j = 0;j < p_max;++j)
			if (left <= Max[j] && Max[j] <= right)
				if (Max[j] > max)
					max = Max[j];
		for (int j = 0;j < p_min;++j)
			if (left <= Min[j] && Min[j] <= right)
				if (Min[j] < min)
					min = Min[j];*/
		for (int j = left;j <= right;++j)
		{
			if (Data[j] > max)
				max = Data[j];
			if (Data[j] < min)
				min = Data[j];
		}
		Merge(max,min);
	}
	
	int DataSize_Q = GetInt(fin);
	int x,y;
	for (int i = 1;i <= DataSize_Q;++i)
	{
		x = GetInt(fin);
		y = GetInt(fin);
		if (FindFather(x) == FindFather(y))
			fprintf(fout,"YES\n");
		else
			fprintf(fout,"NO\n");
	}
	
	fclose(fin);
	fclose(fout);

	return 0;
}
int asd = Main();
int main(){;}