Cod sursa(job #1775908)

Utilizator tanasaradutanasaradu tanasaradu Data 10 octombrie 2016 19:58:10
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
char a[500005];
int b[500005],n,k,cnt;
deque<int>d;
void Citire()
{
    int i,semn=1,numar,x;
    fin>>n>>k;
    cnt=0;
    numar=0;
    fin.get();
    while(fin.getline(a,500000))
    {
        x=strlen(a);
        for(i=0;i<x;)
        {
            if(a[i]=='-')
            {
                semn=-1;
                i++;
            }
            else if(a[i]==' ')
            {
                b[++cnt]=numar*semn;
                numar=0;
                semn=1;
                i++;
            }
            else
            {
                numar=numar*10+(a[i]-'0');
                i++;
            }

        }
        b[++cnt]=numar*semn;
    }
}
void Rezolvare()
{
    int x,minim=-300001,ind,ind1,i;
    for(i=1;i<=k;i++)
    {
        x=b[i];
        while(!d.empty() and b[d.back()]>=x)
            d.pop_back();
        d.push_back(i);
    }
    if(minim<b[d.front()])
    {
        ind=1;
        ind1=i;
        minim=b[d.front()];
    }
    for(i=k+1;i<=cnt;i++)
    {
             x=b[i];
        while(!d.empty() and b[d.back()]>=x)
            d.pop_back();
        d.push_back(i);
        if(i-k>=d.front())
            d.pop_front();
        if(minim<b[d.front()] and i>=k)
        {
            ind1=i;
            minim=b[d.front()];
        }
    }
    ind=ind1-k+1;
    fout<<ind<<" "<<ind1<<" "<<minim<<"\n";
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}