Cod sursa(job #1783420)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 18 octombrie 2016 23:26:02
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector> 
#define MaxN 10005
#define MaxT 66000
#define MaxVal 30000
using namespace std;

FILE *IN,*OUT;

int N,M,v1[MaxN],v2[MaxN],S1,S2,P1,Max,MaxStart,P2,End,Pos,Val,Pi;
struct _DP
{
	unsigned short lenght,father;
}p1[MaxN],p2[MaxN];
struct Tree
{
	unsigned short val,pos;
}T[MaxT];
void Update(int node,int start,int end)
{
	if(start==end)
	{
		T[node].pos=Pi;
		T[node].val=Val;
	}
	else
	{
		int mid=(start+end)>>1;
		if(Pos<=mid)Update(2*node,start,mid);
		else Update(2*node+1,mid+1,end);
		T[node]=T[2*node];
		if(T[node].val<T[2*node+1].val)
			T[node]=T[2*node+1];
	}
}
void Query(int node,int start,int end)
{
	if(end<=End)
	{
		if(Val<T[node].val)
		{
			Val=T[node].val;
			Pos=T[node].pos;
		}
	}
	else
	{
		int mid=(start+end)>>1;
		Query(2*node,start,mid);
		if(End>mid)Query(2*node+1,mid+1,end);
	}
}
void Solve(int *v,_DP *p,int lenght)
{
	Max=0;
	memset(T,0,sizeof T);
	for(int i=1;i<=lenght;i++)
	{
		Val=Pos=0;
		End=v[i];
		Query(1,1,MaxVal);
		p[i].lenght=1+Val;
		p[i].father=Pos;
		if(Max<p[i].lenght)
		{
			Max=p[i].lenght;
			MaxStart=i;
		}
		Pi=i;
		Pos=v[i];
		Val=p[i].lenght;
		Update(1,1,MaxVal);
	}
}
int main()
{
	IN=fopen("adunare.in","r");
	OUT=fopen("adunare.out","w");
	
	fscanf(IN,"%d",&N);
	for(int i=1;i<=N;i++)
		fscanf(IN,"%d",&v1[i]);
	fscanf(IN,"%d",&M);
	for(int i=1;i<=M;i++)
		fscanf(IN,"%d",&v2[i]);
	Solve(v1,p1,N);
	P1=MaxStart,S1=Max;
	Solve(v2,p2,M);
	P2=MaxStart,S2=Max;
	fprintf(OUT,"%d\n",S1+S2);
	return 0;
}