Cod sursa(job #2591350)

Utilizator bem.andreiIceman bem.andrei Data 30 martie 2020 13:03:04
Problema Secventa Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;
ifstream r("secventa.in");
ofstream w("secventa.out");
deque<int>d;
int v[500002];
int main()
{
    int n, k;
    r>>n>>k;
    for(int i=0; i<n; i++)
    {
        r>>v[i];
        if(i<k){
            while(d.size()!=0 && v[i]<=d.back())
            {
                d.pop_back();
            }
            d.push_back(v[i]);
        }
    }
    v[n]=-30001;
    int maxim=-30001, x=0, y=k-1, xf=0, yf=0;
    while(y<n)
    {
            if(v[x]==d.front())
            {
                d.pop_front();
            }
            while(d.size()!=0 && v[y+1]<=d.back())
            {
                d.pop_back();
            }
            d.push_back(v[y+1]);
            if(d.front()>maxim)
            {
                maxim=d.front();
                xf=x+1;
                yf=y+1;
            }
            else if(d.front()==maxim)
            {
                if(x+1<xf)
                {
                    xf=x+1;
                    yf=y+1;
                }
                else if(x+1==xf)
                {
                    if(y+1<yf)
                    {
                        xf=x+1;
                        yf=y+1;
                    }
                }
            }
            x++;
            y++;
    }
    w<<xf+1<<" "<<yf+1<<" "<<maxim;
    return 0;
}