Cod sursa(job #947136)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 6 mai 2013 19:40:48
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <deque>
#include <cstring>

using namespace std;


    char sir[3500012];
int main()
{
    ifstream cin("secventa.in");
    ofstream cout("secventa.out");
int v[500005];

    int k,n,i;
    deque<int> coada;
    cin>>n>>k;
    int baza=-100000;
    int st=-1,dr=-1;
    cin.get();
    cin.get(sir,3500012);
    int x=strlen(sir);
    int poz=0;
    for(i=0;i<x;i++)
        if(sir[i]=='-')
            v[poz]*=(-1);
        else if(sir[i]>='0' && sir[i]<='9')
            v[poz]*=10,v[poz]+=(sir[i]-'0');
        else if(sir[i]==' ')
            poz++;


    for(i=0;i<n;i++)
    {
        while(!coada.empty())
            if((i-coada.front())>=k)
                coada.pop_front();
            else
                break;

        while(!coada.empty())
            if(v[coada.back()]>=v[i])
                coada.pop_back();
            else
                break;
        coada.push_back(i);

        if((i+1)>=k)
        {
            //cout<<v[coada.front()]<<endl;
            if(v[coada.front()]>baza)
            {
                baza=v[coada.front()];
                st=i+2-k;
                dr=i+1;
            }
        }
    }
    cout<<st<<' '<<dr<<' '<<baza<<'\n';

    cin.close();
    cout.close();
    return 0;
}