Cod sursa(job #682164)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 18 februarie 2012 17:30:32
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<iostream>
#include<fstream>
using namespace std;
struct arbore {
	int val,poz;
};
arbore v[400001];
int x[100001],n,poz,val,maxx,a,b;
arbore maxim(arbore a, arbore b)
{
	if(a.val>=b.val)
		return a;
	return b;
}
void update(int nod, int st, int dr)
{
	int mij;
	if(st==dr) {
		v[nod].val=val;
		v[nod].poz=st;
		return;
	}
	mij=(st+dr)/2;
	if(poz<=mij)
		update(2*nod,st,mij);
	else update(2*nod+1,mij+1,dr);
	v[nod]=maxim(v[nod*2],v[nod*2+1]);
}
void query(int nod, int st, int dr)
{
	int mij;
	if((st<=a)&&(b<=dr)&&(x[v[nod].poz]>val)) {
		if(v[nod].val>maxx)
			maxx=v[nod].val;
		return;
	}
	if(st==dr)
		return;
	mij=(st+dr)/2;
	if(a<=mij)
		query(nod*2,st,mij);
	if(mij<b)
		query(2*nod+1,mij+1,dr);
}
void scrie()
{
	int i;
	for(i=1;i<=2*n;i++)
		cout<<v[i].val<<" "<<v[i].poz<<endl;
	cout<<endl;
}
int main ()
{
	int i;
	ifstream f("scmax.in");
	ofstream g("scmax.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>x[i];
	f.close();
	poz=n;
	val=1;
	update(1,1,n);
	for(i=n-1;i>=1;i--) {
		a=i+1;
		b=n;
		maxx=0;
		val=x[i];
		query(1,1,n);
		poz=i;
		val=maxx+1;
		update(1,1,n);
	}
	g<<v[1].val<<'\n';
	maxx=x[v[1].poz]-1;
	for(i=v[1].poz;i<=n;i++)
		if(x[i]>maxx) {
			g<<x[i]<<" ";
			maxx=x[i];
		}
	g.close();
	return 0;
}