Cod sursa(job #1567417)

Utilizator robx12lnLinca Robert robx12ln Data 13 ianuarie 2016 11:02:53
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int v[500005],n,k,minim = (1<<30),st,dr,poz;
deque<int> d;
int main(){
    fin >> n >> k;
    for(int i = 1; i <= n; i++ ){
        fin >> v[i];
    }
    n++;
    v[n] = -(1<<30);
    for( int i = 1 ; i <= k ; i++ ){
        while( !d.empty() ){
            if( v[i] < v[d.back()] )
                d.pop_back();
            else
                break;
        }
        d.push_back(i);
    }
    minim = v[d.front()];
    poz = d.front() + 1;
    d.clear();
    d.push_back(poz-1);
    for( int i = poz; i <= n ; i++ ){
        while( !d.empty() && v[i] < v[d.back()] ){
            if( i - d.back() >= k ){
                if( minim < v[d.back()] ){
                    minim = v[d.back()];
                    st = d.back();
                    dr = i - 1;
                }
            }
            d.pop_back();
        }
        d.push_back(i);
    }
    fout << st << " " << dr << " " << minim;
    return 0;
}