记录编号	142357	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]road	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.434 s
提交时间	2014-12-07 21:00:07	内存使用	27.01 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define sqr(x) ((x)*(x))
const int SIZEN=1000010;
int N;
int ufs[SIZEN]={0};
int grand(int x){return !ufs[x]?x:ufs[x]=grand(ufs[x]);}
pair<int,int> A[SIZEN],B[SIZEN],C[SIZEN];
void merge(int a,int b){
	if(grand(a)!=grand(b)) ufs[grand(a)]=grand(b);
}
void work(void){
	sort(A+1,A+1+N,greater<pair<int,int> >());
	sort(B+1,B+1+N,greater<pair<int,int> >());
	int ans=0;
	for(int i=1;i<=N;i++){
		ans=max(ans,sqr(A[i].first)-sqr(B[i].first));
		merge(A[i].second,B[i].second);
	}
	for(int i=1;i<N;i++) C[i]=make_pair(sqr(A[i].first)-sqr(B[i+1].first),i);
	sort(C+1,C+N);
	for(int i=1;i<N;i++){
		int k=C[i].second;
		if(grand(A[k].second)==grand(B[k+1].second)) continue;
		ans=max(ans,C[i].first);
		merge(A[k].second,B[k+1].second);
	}
	printf("%d\n",ans);
}
void generate(pair<int,int> A[]){
	int MOD=32767,x,y,z;
	for(int i=1;i<=N;i++) A[i].second=i;
	scanf("%d%d%d%d%d",&A[1].first,&A[2].first,&x,&y,&z);
	for(int i=3;i<=N;i++)
		A[i].first=(x*A[i-1].first+y*A[i-2].first+z)%MOD;
}
void read(void){
	scanf("%d",&N);
	generate(A);
	generate(B);
}
int main(){
	freopen("nt2011_road.in","r",stdin);
	freopen("nt2011_road.out","w",stdout);
	read();
	work();
	return 0;
}