Cod sursa(job #1202182)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 27 iunie 2014 10:50:25
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
using namespace std;
#include <fstream>
ifstream fin("secventa.in");
ofstream fout("secventa.out");

const int Kmax = 500000;
const int Nmax = 500000;

char s[3500010];
int v[Nmax+1];
int Q[Kmax+1], first = 0, last = -1;
int poz = 0;

void push(int) ;
int getInt() ;

int main()
{
    int i, k, n, a, MAX = -50000, x, y;
    fin >> n >> k; fin.get();
    fin.getline(s, 3500001);
    for(i = 1; i <= n; ++i) {v[i] = getInt();}
    for(i = 1; i < k; ++i) push(i);
    for(i = k; i <= n; ++i)
    {
        push(i);
        a = v[ Q[first] ];
        if(a > MAX) MAX = a, x = 1+i-k, y = i;
        if(Q[first] == 1+i-k) ++first;
    }
    fout << x << ' ' << y << ' ' << MAX << '\n';
    return 0;
}


void push(int poz)
{
    while(first <= last && v[ Q[last] ] > v[poz]) --last;
    ++last;
    Q[last] = poz;
}

int getInt()
{
    int x = 0, semn = 1;
    if(s[poz] == '-') semn = -1, ++poz;
    while('0' <= s[poz] && s[poz] <= '9')
        x = x * 10 + s[poz] - '0', ++poz;
    ++poz;
    return x * semn;
}