Pagini recente » Cod sursa (job #1677535) | Cod sursa (job #544925) | Cod sursa (job #2703223) | Cod sursa (job #499735) | Cod sursa (job #1070485)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define fiu1 (nod << 1)
#define fiu2 (fiu1 + 1)
#define mid ((st + dr) >> 1)
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
const int Nmax = 100010;
int N, top = 1, sol, v[Nmax], best[Nmax], t[Nmax], a[Nmax], aib[Nmax];
vector <int> rez;
void Update(int poz, int i)
{
while(poz <= top)
{
if(best[i] > best[aib[poz]])
aib[poz] = i;
poz += (poz ^ (poz - 1)) & poz;
}
}
int Query(int poz)
{
int max = 0;
while(poz)
{
if(best[max] < best[aib[poz]])
max = aib[poz];
poz -= (poz ^ (poz - 1)) & poz;
}
return max;
}
int main()
{
fin>>N;
for(int i=1; i<=N; i++)
{
fin>>v[i];
a[i] = v[i];
}
sort(a + 1, a + N + 1);
for(int i=2; i<=N; i++)
if(a[top] != a[i])
a[++top] = a[i];
for(int i=1; i<=N; i++)
{
int poz = lower_bound(a+1, a+top+1, v[i]) - a;
t[i] = Query(poz - 1);
best[i] = best[t[i]] + 1;
Update(poz, i);
if(best[sol] < best[i])
sol = i;
}
fout<<best[sol]<<'\n';
while(sol)
{
rez.push_back(best[sol]);
sol = t[sol];
}
for(int i=rez.size(); i; i--)
fout<<rez[i]<<' ';
return 0;
}