Cod sursa(job #1334799)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 4 februarie 2015 17:42:21
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <cstring>
#define DIM 500002
using namespace std;

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

int n, k, i, p, u, maxim, st, dr, t, f, m, nr;
int v[DIM], d[DIM]; char s[DIM * 6];

void SetUp(){
    fin >> n >> k; nr = 1;
    fin.get();
    fin.get(s + 1, DIM * 6);
    m = strlen(s + 1);
    for(i = 1; i <= m + 100; i ++)
        if(s[i] >= '0' && s[i] <= '9')
            t = t * 10 + (s[i] - '0');
        else
            if(s[i] == '-')
                nr = -1;
            else{
                v[++f] = t * nr;
                t = 0; nr = 1;
            }
    p = 1; u = 1;
    d[1] = 1;
    maxim = -200000;
    return;
}

void Deque(){
    for(i = 2; i <= n; i ++){
        while(p <= u && v[i] < v[d[u]])
            u --;
        d[++u] = i;
        if(i - d[p] == k)
            p ++;
        if(i >= k){
            if(maxim < v[d[p]]){
                maxim = v[d[p]];
                st = i - k + 1;
                dr = i;
            }
        }
    }
    fout << st << " " << dr << " " << maxim;
    return;
}

int main(){
    SetUp();
    Deque();
    return 0;
}