Cod sursa(job #2229746)

Utilizator antracodsAntracod antracods Data 8 august 2018 01:29:38
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

deque <int> deck;

const int NMAX = 500000;
int v[NMAX+2],p;

#define f first
#define s second
char s[3000100];
void read(int &x) {
    x=0;
    bool sign=false;
    if(s[p]=='-')
        sign=true,p++;
    while(s[p]>='0'&&s[p]<='9')
        x=x*10+(s[p]-'0'),p++;
    p++;
    if(sign)
        x*=-1;
}



int main()
{
    int n,k;
    in.getline(s,3000100);
    read(n);
    read(k);
    in.getline(s,3000100);
    p=0;
    for(int i=1;i<=n;i++)
    {
        int m;
        read(m);
        v[i]=m;
    }
    for(int i=1;i<k;i++)
    {
        while(deck.empty()!=1 && v[i]<=v[deck.back()])
        {
            deck.pop_back();
        }
        deck.push_back(i);
    }
    int isol=k;
    int sol=-30001;
    for(int i=k;i<=n;i++)
    {
        while(deck.empty()!=1 && v[i]<=v[deck.back()])
        {
            deck.pop_back();
        }
        deck.push_back(i);
        while(deck.front()<=i-k)
        {
            deck.pop_front();
        }
        if(v[deck.front()]>sol)
        {
            sol=v[deck.front()];
            isol=i;
        }
    }
    out<<isol-k+1<<" "<<isol<<" "<<sol;
}