Cod sursa(job #1311259)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 7 ianuarie 2015 21:41:10
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <deque>
std::deque <int> val,pos;
#define DIM 10000
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()
{
    freopen ("secventa.in","r",stdin);
    freopen ("secventa.out","w",stdout);
    int n;
    int k;
    int nr;
    citeste(n);
    citeste(k);
    for(int i=1;i<k;i++)
    {
            citeste(nr);
            while(!val.empty()&&val.back()>nr)
            {
                                              val.pop_back();
                                              pos.pop_back();
            }
            val.push_back(nr);
            pos.push_back(i);
    }
    int max=-30001,maxp;
    for(int i=k;i<=n;i++)
    {
            while(pos.front()<=i-k)
            {
                                val.pop_front();
                                pos.pop_front();
            }
            citeste(nr);
            while(!val.empty()&&val.back()>=nr)
            {
                                              val.pop_back();
                                              pos.pop_back();
            }
            val.push_back(nr);
            pos.push_back(i);
            if(max<val.front())
            {
                                max=val.front();
                                maxp=i;
            }
    }
    printf("%d %d %d\n",maxp-k+1,maxp,max);
    return 0;
}