Pagini recente » Cod sursa (job #1035464) | Monitorul de evaluare | Cod sursa (job #2804889) | Cod sursa (job #1554745) | Cod sursa (job #2303606)
#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 minim;
}node;
node T[262144];
int L;
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;
if(T[index*2].minim==0){
T[index].minim=0;
return;
}
if(T[index*2+1].minim==0){
T[index].minim=T[index*2].minim;
return;
}
if(T[index*2].minim < T[index*2+1].minim)
T[index].minim=T[index*2].minim;
else
T[index].minim=T[index*2+1].minim;
}
int value;
int findmaxidx(int index){
int l=T[index].left;
int r=T[index].right;
if(l==r)
return l;
int mid=(l+r)/2;
if(T[index*2+1].minim!=0 && T[index*2+1].minim < value)
return findmaxidx(index*2+1);
else
return findmaxidx(index*2);
}
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);
if(T[idx].minim < V[i]){
k=findmaxidx(idx);
if((B[k]+1)>B[i]){
B[i]=B[k]+1;
P[i]=k;
}
}
begin+=(1<<j);
}
}
if(B[i]>bestlung){
bestlung=B[i];
bestindex=i;
}
}
}
int main(){
freopen("scmax.in", "r", stdin);
//freopen("scmax_test1.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].minim=V[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;
}