Cod sursa(job #2190281)

Utilizator codrin18Diac Eugen Codrin codrin18 Data 30 martie 2018 13:35:05
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <cmath>
#define nmax 500005
#define For(i,a,b) for (int i=(a);i<=(b);++i)
using namespace std;
deque <int> dq;
int v[nmax],n,k;
int main()
{
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    int m=0;
    fin>>n>>k;
    For(i,1,n)
       fin>>v[i];
    For(i,1,n)
    {
        while(!dq.empty() and v[dq.back()]>=v[i]) dq.pop_back();/// Cat timp elementul curent este mai mic decat ultimul element din deque, eliminam pozitia ultimului element din deque
        dq.push_back(i);///adaugam pozitia elementului curent in dq
    }
    m=v[dq.front()];
    For(i,k+1,n)
    {
        if (i-dq.front()>=k) dq.pop_front();
        while(!dq.empty() and v[dq.back()]>=v[i]) dq.pop_back();
        dq.push_back(i);
        m=max(m,v[dq.front()]);
    }
    For (i,1,n)
    {
        if (v[i]==m)
        {
            int l=1;
            int q=i-1;
            while(v[q]>=m && q>=1)
            {
                q--;
                l++;
            }
            int p=i+1;
            if (l>=k)
            {
                fout<<q+1<<" "<<i<<" "<<m;
                return 0;
            }
           while(v[p] >= m && p <= n)
            {
                p++;
                l++;
                if (l >= k)
                {
                    fout <<q+1<<" "<<p-1<<" "<<m;
                    return 0;
                }
           }
        }

    }
    return 0;
}