Cod sursa(job #1973699)

Utilizator bucuralexandraioana05Bucur Alexandra bucuralexandraioana05 Data 25 aprilie 2017 18:43:14
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include<fstream>
#include<deque>
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");
deque<int> dq;
int n,i,j,k,v[500001],a;
int main()
{

     long long ans = -1000000000;
    f>>n>>k;
    for( i = 1 ; i <= n ; i++ )
        f>>v[ i ];
    for( i = 1 ; i < k ; i++ )
    {
        while( dq.size() && v[ i ] <= v[ dq.front() ] )
            dq.pop_front();
        dq.push_front( i );
    }
    for( i = k ; i <= n ; i++ )
    {
        while( dq.size() && v[ i ] <= v[ dq.front() ] )
            dq.pop_front();
        dq.push_front( i );
        if( v[ dq.back() ] > ans )
        {
            ans = v[ dq.back() ];
            a = i;
        }
        if( dq.back() == i - k + 1 )
            dq.pop_back();
    }
    g<<a-k+1<<' '<<a<<' '<<ans;
    return 0;
}