Pagini recente » Cod sursa (job #2745079) | Cod sursa (job #2283645) | Cod sursa (job #1659543) | Cod sursa (job #1720749) | Cod sursa (job #2080853)
#include<stdio.h>
#include<utility>
#define MAXN 100000
void update(int nod,int st,int dr);
int poz; //updates the tree by taking v[poz] into consideration
int query(int nod,int st,int dr);
int queryst,querydr; //queries for the index of the max in the specified interval,that also obliges to special conditions,returns -1 if no such index exists
FILE*fin,*fout;
int arbint[4*MAXN+1];
int v[MAXN+1];
std::pair<int,int> best[MAXN+1];
int main()
{
fin=fopen("scmax.in","r");
fout=fopen("scmax.out","w");
int N;
fscanf(fin,"%d",&N);
int bestpoz=0;
for(int i=1; i<=N; i++)
{
fscanf(fin,"%d",&v[i]);
poz=i;
update(1,1,N);
}
for(int i=1;i<=N;i++)
{
queryst=1;
querydr=i-1;
int q=query(1,1,N);
if(q==-1)
{
best[i].first=1;
best[i].second=-1;
}
else
{
best[i].first=best[q].first+1;
best[i].second=q;
}
if(best[bestpoz].first<best[i].first)
{
bestpoz=i;
}
}
int afis[MAXN+1],ult=-1;
fprintf(fout,"%d\n",best[bestpoz].first);
for(int i=bestpoz;i!=-1;i=best[i].second)
{
afis[++ult]=i;
}
for(int i=ult;i>=0;i--)
{
fprintf(fout,"%d ",v[afis[i]]);
}
fclose(fin);
fclose(fout);
}
void update(int nod,int st,int dr)
{
if(st==dr)
{
arbint[nod]=poz;
return;
}
int mij=(st+dr)>>1;
if(poz<=mij)
{
update(2*nod,st,mij);
}
else
{
update(2*nod+1,mij+1,dr);
}
int son=v[arbint[2*nod]]>v[arbint[2*nod+1]]?(2*nod):(2*nod+1);
arbint[nod]=arbint[son];
}
int query(int nod,int st,int dr)
{
int mij=(st+dr)>>1;
if(st>querydr || dr<queryst)
{
return -1;
}
if(queryst<=st && dr<=querydr)
{
if(v[querydr+1]>v[arbint[nod]])
{
return arbint[nod];
}
}
if(st==dr)
{
return -1;
}
int a=query(2*nod,st,mij);
int b=query(2*nod+1,mij+1,dr);
if(a==-1)
{
return b;
}
if(b==-1)
{
return a;
}
if(a==-1 && b==-1)
{
return -1;
}
return v[a]>v[b]?a:b;
}