Cod sursa(job #2062362)

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

    int n,k;
    int *v;
    ifstream fin("secventa.in");
    fin>>n>>k;
    fin.get();
    fin.getline(buf,dim);
    v=new int[n+1];
    int i;
    int l=0;
    int semn=0;
    int numar=0;
    for(i=0;buf[i]!=0;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;
    for(int i=1;i<=k;i++){
         for(;!d.empty() && v[i]<=v[d.front()];)
            d.pop_front();
        d.push_front(i);}
    int sol=d.front();
    int prim,ultim;
    for(i=k+1;i<=n;i++){
        for(;!d.empty() && v[i]<=v[d.front()];)
            d.pop_front();
        d.push_front(i);
        if(!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;
}