Cod sursa(job #2589459)

Utilizator JesseMcCreeVladimir Sontea JesseMcCree Data 26 martie 2020 13:14:49
Problema Secventa Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

FILE *fin, *fout;

short int v[500001];
int dq[500001];

int main()
{
    fin=fopen("secventa.in", "r");
    fout=fopen("secventa.out", "w");

    int n, k, fr=1, b=0, lmax=-40000, i2, j2, min2;
    fscanf(fin, "%d%d", &n, &k);
    for(int i=1; i<=n; i++)
    {
        fscanf(fin, "%d", &v[i]);
    }
    for(int kk=k; kk<=n; kk++)
    {
        for(int i=1; i<=n; i++) dq[i]=0;
        fr=1;
        b=0;
        for(int i=1; i<=n; i++)
        {
            while(fr<=b && v[i]<=v[dq[b]]) b--;
            dq[++b]=i;

            if(dq[fr]==i-kk)
            {
                fr++;
            }
            if(i>=kk)
            {
              //printf("minimul secv de %d elemente care incepe cu %d este %d\n", kk, i-kk+1, v[dq[fr]]);
              if(v[dq[fr]]>lmax)
              {
                i2=i-kk+1;
                j2=i;
                min2=v[dq[fr]];
                lmax=v[dq[fr]];
              }
            }
        }
    }

    fprintf(fout, "%d %d %d", i2, j2, min2);

    fclose(fin);
    fclose(fout);
    return 0;
}