Cod sursa(job #1014448)

Utilizator stefanzzzStefan Popa stefanzzz Data 22 octombrie 2013 18:48:02
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <deque>
#define MAXN 500005
#define INF 50000
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");

int n,k,v[MAXN],mx,mxi;
deque<int> dq;

int main()
{
    int i;
    f>>n>>k;
    mx=-INF;
    for(i=1;i<=n;i++)
        f>>v[i];
    for(i=1;i<=k-1;i++){
        while(!dq.empty()&&v[dq.back()]>=v[i])
            dq.pop_back();
        dq.push_back(i);}
    for(i=k;i<=n;i++){
        while(!dq.empty()&&v[dq.back()]>=v[i])
            dq.pop_back();
        dq.push_back(i);
        while(dq.front()<i-k+1)
            dq.pop_front();
        if(v[dq.front()]>mx){
            mx=v[dq.front()];
            mxi=i;}}
    g<<mxi-k+1<<' '<<mxi<<' '<<mx<<'\n';
    f.close();
    g.close();
    return 0;
}