Cod sursa(job #894561)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 26 februarie 2013 22:02:28
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <cstring>
#include <iostream>
#include <deque>
#define INF 2000000000

using namespace std;

int n, k, a[500010], start, finish, baza = -INF;
char ch[3500000];
deque <int> d;

int main()
{
    int i, x, ind = 0, semn;
    ifstream f ("secventa.in");
    f>>n>>k;
    f.get();
    f.getline(ch, 3500000);
    for (i=1; i<=n; i++)
    {
        while (ch[ind] && ch[ind] == ' ')
            ind++;
        if (ch[ind] == '-')
            semn = -1, ind++;
        else
            semn = 1;
        x = 0;
        while (ch[ind] && ch[ind] >= '0' && ch[ind] <= '9')
            x=x*10+(ch[ind] - '0'), ind++;
        a[i] = x*semn;
        while (!d.empty() && a[i] <= a[d.back()])
        {
            d.pop_back();
        }
        d.push_back(i);

        if (d.front () == i-k)
            d.pop_front();

        if (i>=k)
        {
            if (a[d.front()] > baza)
            {
                baza = a[d.front()];
                start = i-k+1;
                finish = i;
            }
        }
    }
    f.close();

    while (start > 1 && a[start-1] >= baza)
        start--;

    ofstream g("secventa.out");
    g<<start<<" "<<finish<<" "<<baza<<"\n";
    g.close();


    return 0;
}