Cod sursa(job #1775925)

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

        }
       if(cnt<n) a[++cnt]=numar*semn;
    }
}
void Rezolvare()
{
    int i,x,minim=-30005,inceput,sfarsit;
    Citire();
    for(i=1;i<=n;i++)
    {
        x=a[i];
        while(!q.empty() and a[q.back()]>=x)
            q.pop_back();
        q.push_back(i);
        if(i-k>=q.front())
            q.pop_front();
           if(minim<a[q.front()] and i>=k)
        {
            minim=a[q.front()];
            sfarsit=i;
        }
    }
    inceput=sfarsit-k+1;
    fout<<inceput<<" "<<sfarsit<<" "<<minim<<"\n";
    fin.close();
    fout.close();
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}