Cod sursa(job #812532)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 13 noiembrie 2012 22:52:41
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <utility>
#include <queue>
using namespace std;

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

deque<pair<int,int> > q;
int n,k,a[500010],i,li,ls,m,sgn;

int main() {
    in>>n>>k;
    int s = in.tellg();
    in.seekg(0, ios::end);
    int e = in.tellg();
    in.seekg(s);
    char *c = new char[e-s+2];
    c[e-s+1] = c[0] = ' ';
    in.read(c+1, e-s+10);

    m = -(1<<29);
    int j=0;
    for(i=1; i<=n; i++) {
        while((c[j] < '0'  || c[j] > '9') && c[j] != '-')
            j++;

        if(c[j] == '-')
            sgn = -1, j++;
        else
            sgn = 1;

        while(j < (e-s+1) && (c[j] >= '0' && c[j] <= '9'))
            a[i] = a[i] * 10 + (c[j++] - '0');
        a[i] *= sgn;

        while(!q.empty() && q.back().first >= a[i]) {
            q.pop_back();
        }
        q.push_back(make_pair(a[i], i));
        while(q.front().second <= i-k) {
            q.pop_front();
        }
        if(i >= k && m < q.front().first) {
            m = q.front().first;
            li = i-k+1;
            ls = i;
        }
    }
    while(li > 1 && a[li-1] >= m)
        li--;
    out<<li<<' '<<ls<<' '<<m;
    return 0;
}