Cod sursa(job #1270343)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 22 noiembrie 2014 11:42:11
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <deque>
#include <stdio.h>

struct str
{
       long int val,pos;
} v[500001];

std::deque<str> d;

int main()
{
    FILE *fin,*fout;
    fin=fopen("secventa.in","r");
    fout=fopen("secventa.out","w");
    long int n,k,max=-31000,p1;
    fscanf(fin,"%ld %ld",&n,&k);
    for(int i=1;i<=n;i++)
    {
            fscanf(fin,"%ld",&v[i].val);
            v[i].pos=i;
    }
    for(int i=1;i<k;i++)
    {
            while(d.size()&&d.back().val>v[i].val)
            {
                                                  d.pop_back();
            }
            d.push_back(v[i]);
    }
    for(int i=k;i<=n;i++)
    {
            if(d.front().pos<=i-k)
            {
                                  d.pop_front();
            }
            while(d.size()&&d.back().val>v[i].val)
            {
                                                  d.pop_back();
            }
            d.push_back(v[i]);
            
            if(max<d.front().val)
            {
                                 max=d.front().val;
                                 p1=d.front().pos;
            }
    }
    fprintf(fout,"%ld %ld %ld\n",p1,p1+k-1,max);
}