Cod sursa(job #2227962)

Utilizator LIR16LazarIonutRadu LIR16 Data 2 august 2018 12:48:57
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream>
#include<deque>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

deque < pair <int, int> > Deque;
int V[500003],N,K,Min=-30005,Sol;
char Sir[4000000];

int Comp(int Nr)
{
    while(!Deque.empty() && Nr<Deque.back().first)
    {
        Deque.pop_back();
    }
}

int Cut(int i)
{
    while(!Deque.empty() && Deque.front().second<(i-K+1))
        Deque.pop_front();
}

void Read()
{
    fin.getline(Sir,3900000);
    int Nr=0,Ind=0,Semn=1;
    for(int i=0; Sir[i]; i++)
        if(Sir[i]=='-')
            Semn=-1;
        else if(Sir[i]==' ')
        {
            Ind++;
            V[Ind]=Nr*Semn;
            Nr=0;
            Semn=1;
        }
        else
        {
            Nr=Nr*10+(Sir[i]-'0');
        }
    V[N]=Semn*Nr;
}
int main()
{
    fin>>N>>K;
    fin.getline(Sir,100);
    Read();
    for(int i=1; i<=N; i++)
    {
        Comp(V[i]);
        Cut(i);
        Deque.push_back(make_pair(V[i],i));
        if(Deque.front().first>Min && i>K-1)
        {
            Sol=i;
            Min=Deque.front().first;
        }
    }
    fout<<Sol-K+1<<" "<<Sol<<" "<<Min<<'\n';
}