Pagini recente » Cod sursa (job #546964) | Cod sursa (job #1949554) | Cod sursa (job #1506891) | Cod sursa (job #387836) | Cod sursa (job #2303691)
#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;
}