Cod sursa(job #821150)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 21 noiembrie 2012 20:08:22
Problema Subsir crescator maximal Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#define NM 100001
int N,v[NM],prev[NM],last[NM],poz,maxx,pmax,nr;
inline void citire()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&N);
	int i;
	for (i=1; i<=N; ++i)
		scanf("%d",&v[i]);
}
inline void citire2(char s1[],char s2[]) {
	freopen(s1,"r",stdin);
	freopen(s2,"w",stdout);
	scanf("%d",&N);
	int i;
	for (i=1; i<=N; ++i)
		scanf("%d",&v[i]);
}
inline int caut(int x) {
	int p=1,u=nr,m,pok=nr;
	while (p<=u) {
		m=(p+u)>>1;
		if (v[last[m]]<=x)
			p=m+1;
		else {
			u=m-1;
			pok=m;
		}
	}
	return pok;
}
inline int maxim(int a, int b)
{
	if (a>b) return a;
	return b;
}
inline void afis(int i) {
    if (prev[i]) {
        afis(prev[i]);
    }
    printf("%d ",i);
}
inline void scmax()
{
	last[1]=1;
	nr=1;
	int i;
	for (i=2; i<=N; ++i) {
		if (v[i]>=v[last[nr]])
			poz=nr+1;
		else
			poz=caut(v[i]);
		prev[i]=last[poz-1];
		last[poz]=i;
		nr=maxim(nr,poz);
		if (nr>maxx) {
			maxx=nr;
			pmax=i;
		}
	}
	printf("%d\n",maxx);
	afis(pmax);

}

int main(int n,char *arg[]) {
	citire();
	//citire2(arg[1],arg[2]);
	scmax();
	return 0;
}