Cod sursa(job #2190217)

Utilizator codrin18Diac Eugen Codrin codrin18 Data 30 martie 2018 08:47:27
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#define For(i,a,b) for (int i=(a);i<=(b);++i)
#define maxn 500005
using namespace std;
int n,k,A[maxn],Front=0,Back=1,Deque[maxn],mx=0,p;
int main()
{
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    fin>>n>>k;
    For(i,1,n)
       fin>>A[i];
    For(i,1,n)
    {
        /// Cat timp elementul curent este mai mic decat ultimul element din deque, eliminam pozitia ultimului element din deque
        while (Front <= Back && A[i] <= A[ Deque[Back] ]) Back--;
        /// Adaugam pozitia elementului curent in deque
        Deque[++Back] = i;

        /// Daca elementul minim coincide cu cel de pe pozita i-K, ii eliminam pozitia din deque, deoarece acesta nu mai conteaza pentru pasii >= i
        if (Deque[Front] == i-k) Front++;
        /// Afisam minimul, acesta aflandu-se in varful deque-ului
        if (i>=k) {mx=max(mx,A[Deque[Front]]);p=Deque[Front];}
    }
    For (i,p-k+1,p)
    {
            bool ok=false;
        For (j,i,i+k-1)
        {
            if (A[i]<mx) ok=true;
        }
        if (ok==false) {fout<<i<<" "<<i+k-1<<" "<<mx;break;}
    }
    return 0;
}