Pagini recente » Cod sursa (job #243473) | Cod sursa (job #1479251) | Cod sursa (job #255226) | Cod sursa (job #2901378) | Cod sursa (job #682164)
Cod sursa(job #682164)
#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;
}