Cod sursa(job #1235013)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 28 septembrie 2014 15:56:32
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <cstdio>
using namespace std;
FILE *f=fopen ("secventa.in","r");
FILE *g=fopen ("secventa.out","w");

int a[500010],b[500010],maxx=0,ma,n,pozi,pozf,st[500010],dr[500010];

void Solve()
{
int j,i,k=0;
for (i=1;i<=n;i++)
{
while (k>0 && a[i]<=a[b[k]]) k--;
k++;
b[k]=i;
for (j=k;j>=1;j--)
{
    if (i-b[j]+1>=ma) {if (a[b[j]]>maxx) {maxx=a[b[j]];pozi=b[j]+1;pozf=i;}break;}
}


}





}

void PrimSt()
{
    int i;
    int k=0;
    for (i=1;i<=n;i++)
    {
    while (k>0 && a[i]<=a[b[k]]) k--;
    k++;
    b[k]=i;
    st[i]=b[k-1];

    }
}

void PrimDr()
{
        int i;
        b[0]=n;
    int k=0;
    for (i=n;i>=1;i--)
    {
    while (k>0 && a[i]<=a[b[k]]) k--;
    k++;
    b[k]=i;
    dr[i]=b[k-1];

    }
}


int main()
{
    int i;
fscanf (f,"%d %d",&n,&ma);
for (i=1;i<=n;i++) {
fscanf (f,"%d",&a[i]);

}
PrimSt();
PrimDr();

for (i=1;i<=n;i++)
{
    if (dr[i]-st[i]>=ma && maxx<a[i]) {pozi=st[i]+1;pozf=dr[i];maxx=a[i];}
    if (dr[i]-st[i]>=ma && maxx==a[i]) {if (st[i]<pozi) {pozi=st[i]+1;pozf=dr[i];maxx=a[i];}
    if (st[i]==pozi && dr[i]<=pozf) {pozi=st[i]+1;pozf=dr[i];maxx=a[i];}  }
}
fprintf (g,"%d %d %d",pozi,pozf,maxx);

    return 0;
}