Cod sursa(job #2922481)

Utilizator Theo14Ancuta Theodor Theo14 Data 8 septembrie 2022 17:16:19
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include<bits/stdc++.h>
using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n,v[100005],aib[100005],maxi=INT_MIN;

void update(int a, int b)
{
    int i;
    for(i=a;i<=maxi;i+=(i&-i))
        aib[i]+=b;
}

int query(int l)
{
    int i,s=0;
    for(i=l;i>=1;i-=(i&-i))
        s+=aib[i];
    return s;
}

int main()
{
    int i,val,maxi1=INT_MIN;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i],maxi=max(maxi,v[i]);
    for(i=1;i<=n;i++)
    {
        update(v[i],1);
        val=query(maxi)-query(v[i]-1);
        maxi1=max(maxi1,val);
    }
    g<<maxi1;
    return 0;
}