Cod sursa(job #2080853)

Utilizator PinkiePie1189Preoteasa Mircea-Costin PinkiePie1189 Data 3 decembrie 2017 16:20:26
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#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;
}