Pagini recente » Cod sursa (job #1291491) | Cod sursa (job #200748) | Cod sursa (job #687614) | Cod sursa (job #2014372) | Cod sursa (job #609506)
Cod sursa(job #609506)
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,i,a[100005],best[100005],ant[100005],ArbInt[524290],ArbInt2[524290],val,poz,maxim,start,final;
void update(int, int, int);
void query(int, int, int);
int main () {
f >> n;ant[1]=ant[0]=-1;
f >> a[1];val=poz=best[1]=1;update(1,1,n);
for (i=2;i<=n;i++) {
f >> a[i];poz=i;val=a[i];start=1;final=i-1;
query(1,1,n);
best[i]=maxim+1;val=best[i];
update(1,1,n);
}
i=n+2;start=1;final=n;
query(1,1,n);
g << maxim << '\n';
int k=0;
while (ant[i]>-1) {
g << ant[i] << ' ';
i=ant[i];
}
for (i=k;i>=1;i--) g << a[best[i]] << ' ';
f.close();g.close();
return 0;
}
void update (int nod,int stanga,int dreapta) {
if (stanga==dreapta) {
ArbInt[nod]=val;ArbInt2[nod]=poz;
return;
}
int mij=(stanga+dreapta)/2;
if (poz<=mij) update(2*nod,stanga,mij);
else update(2*nod+1,mij+1,dreapta);
ArbInt[nod]=max(ArbInt[2*nod],ArbInt[2*nod+1]);
if (ArbInt[2*nod]>ArbInt[2*nod+1]) {
ArbInt[nod]=ArbInt[2*nod];ArbInt2[nod]=ArbInt2[2*nod];
}
else {
ArbInt[nod]=ArbInt[2*nod+1];ArbInt2[nod]=ArbInt2[2*nod+1];
}
}
void query (int nod,int stanga,int dreapta) {
if (start<=stanga && dreapta<=final) {
if (maxim<ArbInt[nod]) {
if (val>=a[ArbInt2[nod]]) {maxim=ArbInt[nod];ant[i]=ArbInt2[nod];}
}
return;
}
int mij=(stanga+dreapta)/2;
if (start<=mij) query(2*nod,stanga,mij);
if (mij<final) query(2*nod+1,mij+1,dreapta);
}