Cod sursa(job #2062377)

Utilizator CroitoruAlinCroitoru Alin CroitoruAlin Data 10 noiembrie 2017 12:09:42
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
int dim=2000000;
char buf[2000000];
int main()
{

    int n,k;

    ifstream fin("secventa.in");
    fin>>n>>k;
    int *v=new int[n+1];
    fin.get();
    fin.getline(buf,dim);
    int i;
    int l=0;
    int semn=0;
    int numar=0;
    for(i=0;buf[i]!=0 && i<dim;i++)
        if(buf[i]=='-')
    {
        semn=1;
    }
    else
        if(buf[i]==' ')
    {
        if(semn==1)
            numar=-numar;
        l++;
        v[l]=numar;
        numar=0;
        semn=0;
    }
    else
    {
        numar=numar*10+(buf[i]-'0');
    }
    l++;
    v[l]=numar;

    deque<int> d;
    int sol=-31000;
    int prim,ultim;
    for(i=1;i<=n;i++){
        for(;!d.empty() && v[i]<=v[d.front()];)
            d.pop_front();
        d.push_front(i);
        while(!d.empty() && i-k>=d.back())
            d.pop_back();
        if(k<=i && v[d.back()]>sol)
        {
            sol=v[d.back()];
            prim=i-k+1;
            ultim=i;
        }
    }
    ofstream fout("secventa.out");
    fout<<prim<<" "<<ultim<<" "<<sol;
    fout.close();
    delete[] v;
    return 0;
}