Cod sursa(job #655518)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 2 ianuarie 2012 19:34:30
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

string m;
deque <int> mind;
int n,k,i,a[500001],j,mx=-50000,s,l;

void pushm(int i) {
    while (!mind.empty() && a[i]<=a[mind.back()]) mind.pop_back();
    mind.push_back(i);
}

int main () {
    f >> n >> k;
    f.get();
    getline(f,m);
    j=-1;
    for (i=1;i<=n;i++) {
        j++;s=0;l=1;
        if (m[j]=='-') {l=-1;j++;}
        while (m[j]>='0' && m[j]<='9') {
            s=s*10+int(m[j])-int('0');
            j++;
        }
        a[i]=s*l;
    }
    i=j=1;
    while (i<=n && j<=i) {
        pushm(i);
        while (i-j+1>k) {
            if(!mind.empty() && mind.front()<=j) mind.pop_front();
            j++;
        }
        if (i-j+1==k && mx<a[mind.front()]) {
            mx=a[mind.front()];
            s=j;
        }
        i++;
    }
    g << s << ' ' << s+k-1 << ' ' << mx << '\n';
    f.close();g.close();
    return 0;
}