Pagini recente » Istoria paginii runda/kontrollarbeit | Istoria paginii utilizator/abu_cita | Cod sursa (job #2037512) | Cod sursa (job #1006884) | Cod sursa (job #2483800)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100003;
int A[NMAX],best[NMAX],poz[NMAX];
pair<int,int> arb[2*NMAX];
int n;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
void update(int index,int value)
{
index+=n;
arb[index].second=value;
while(index)
{
index/=2;
if(arb[2*index].second>arb[2*index+1].second)
{
arb[index] = arb[2*index];
}
else
{
arb[index] = arb[2*index+1];
}
}
}
pair<int,int> query(int left,int right)
{
pair<int,int> maximum = {-1,-19231};
left+=n;
right+=n;
while(left<right)
{
if(left%2)
{
if(maximum.second<arb[left].second)
{
maximum = arb[left];
}
left++;
}
if(right%2)
{
right--;
if(maximum.second<arb[right].second)
{
maximum = arb[right];
}
}
left/=2,right/=2;
}
return maximum;
}
void construct()
{
for(int i = n-1;i>0;i--)
arb[i]=max(arb[2*i],arb[2*i+1]);
}
int main()
{
construct();
int maxim = 1,p=n;
fin>>n;
for(int i = 1;i<=n;i++)
{
fin>>A[i];
arb[i+n-1].first = i;
}
best[n]=1;
update(n-1,1);
poz[n]=-1;
for(int i = n-1;i>=1;i--)
{
best[i]= 1;
poz[i]=-1;
int j = query(i,n).first;
if(A[i]<A[j] && best[i]<best[j]+1)
{
best[i] = best[j]+1;
update(i-1,best[j]+1);
poz[i]=j;
if(best[i]>maxim)
{
maxim = best[i];
p = i;
}
}
}
vector<int> r;
while(p!=-1)
{
r.push_back(A[p]);
p = poz[p];
}
fout<<r.size()<<'\n';
for(int i = 0;i<r.size();i++)
fout<<r[i]<<" ";
return 0;
}