Cod sursa(job #1736345)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 1 august 2016 16:37:48
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#define DIM 10000

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

struct qq{int val; int id;};

qq deq[500005];

int n, k, i, bk, fr, x, fi;
int sum;
char buff[DIM];
int poz=0;

void citeste(int &numar)
{
     numar = 0;
     char semn='+';
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          semn = buff[poz];
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     if (semn == '-')
          numar = -numar;
}

int main()
{
    citeste(n);
    citeste(k);
    fr=1; bk=0;
    deq[0].val=(-1)*1000000;
    sum=(-1)*1000000;
    for (i=1; i<=n; i++)
    {
        citeste(x);
        while (bk >= fr && deq[bk].val>=x)
            bk--;
        deq[++bk].val=x;
        deq[bk].id=i;
        while (fr <= bk && deq[fr].id<=i-k)
            fr++;
        if (k<=i)
        {
            if(deq[fr].val>sum)
            {
                sum=deq[fr].val;
                fi=i;
            }
        }
    }
    fout<<fi-k+1<<" "<<fi<<" "<<sum;
    return 0;
}