Cod sursa(job #2303691)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 16 decembrie 2018 19:04:15
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.6 kb
#include<stdio.h>
 
#include<iostream>
#include<fstream>
 
using namespace std;
  
#define MAXN 100000
  
int N;
int V[MAXN+1];
int B[MAXN+1];
int P[MAXN+1];

typedef struct node{
	int left;
	int right;
	int maxim;
	int index;
}node;

node T[262144];
int L;

void updatetree(int index){
	if(index==0)
		return;
	if(T[index].maxim >= T[index*2].maxim && T[index].maxim >= T[index*2+1].maxim){
		return;
	}
	if(T[index*2].maxim > T[index*2+1].maxim){
		T[index].maxim=T[index*2].maxim;
		T[index].index=T[index*2].index;	
	}
	else{
		T[index].maxim=T[index*2+1].maxim;
		T[index].index=T[index*2+1].index;	
	}
	updatetree(index/2);
}

void builtree(int left,int right,int index){
	if(left==right)
		return;
	if(left>N)
		return;
	int mid=(left+right)/2;
	builtree(left,mid,index*2);
	builtree(mid+1,right,index*2+1);
	T[index].left=left;
	T[index].right=right;
}	

int value;
int findbestidx(int index){
	if(V[T[index].index] < value){
		return T[index].index;
	}	
	int l=T[index].left;
	int r=T[index].right;
	if(l==r){
		if(V[T[index].index] < value)
			return T[index].index;	
		else
			return 0;
	}

	int bestidx1=findbestidx(index*2);
	int bestidx2=findbestidx(index*2+1);
	if(B[bestidx1] > B[bestidx2])
		return bestidx1;
	else
		return bestidx2;
}

int bestlung=1;
int bestindex=1;

void computeBest(){
	int mask,bit;
	int level;
	int idx,k;
	for(int i=2;i<=N;i++){
		int begin=1;
		B[i]=1; P[i]=-1;
		value=V[i];
		for(int j=L-1;j>=0;j--){
			mask=1<<j;
			bit=(i-1) & mask;
			bit>>=j;
			if(bit){
				level=L-j;
				idx=(1<<level)+((begin-1)>>j);
				k=findbestidx(idx);
				if((B[k]+1)>B[i]){
					B[i]=B[k]+1;
					P[i]=k;
				}
				begin+=(1<<j);
			}
		}
		
		T[(1<<L)+i-1].maxim=B[i];
		updatetree(((1<<L)+i-1)/2);

		if(B[i]>bestlung){
			bestlung=B[i];
			bestindex=i;
		}
	}
}

int main(){
	
	freopen("scmax.in", "r", stdin);
	//freopen("scmax_test3.in", "r", stdin);
	freopen("scmax.out", "w", stdout);
 
	scanf("%d",&N);
 
	for(int i=1;i<=N;i++){
		scanf("%d", &V[i]);
	}
 
	int pw=1;
	while(pw<N){
		pw*=2; L++;
	}

	int crt=1<<L;
	for(int i=1;i<=N;i++){
		T[crt+i-1].left=i;
		T[crt+i-1].right=i;
		T[crt+i-1].maxim=1;
		T[crt+i-1].index=i;
	}

	builtree(1,1<<L,1);

	B[1]=1;
	P[1]=-1;

	computeBest();

	printf("%d\n",bestlung);

	int* pozitii=new int[bestlung];
	int lung=bestlung-1;
	int pozbest=bestindex;

	while(lung>=0){
		pozitii[lung]=pozbest;
		pozbest=P[pozbest];
		lung--;
	}
 
	for(int i=0;i<bestlung;i++)
		printf("%d ",V[pozitii[i]]);
	printf("\n");

	return 0;
}