Cod sursa(job #1254856)

Utilizator diana97Diana Ghinea diana97 Data 3 noiembrie 2014 16:55:59
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <cstring>

using namespace std;

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

const int NMAX = 500000 + 1;
const int INF = 1 << 30;
int n, k;
int v[NMAX];
char s[3500001];
deque <int> D;

void rezolva() {
    int sol = -INF, begin = 0;
    for (int i = 1; i <= n; i++) {
        while (!D.empty() && v[D.back()] > v[i]) D.pop_back();
        D.push_back(i);
        if (i - D.front() >= k) D.pop_front();
        if (i >= k - 1 && v[D.front()] > sol) {
           // cout << 1;
            sol = v[D.front()];
            begin = i - k + 1;
        }
    }
    g << begin << ' ' << begin + k - 1 << ' ' << sol << '\n';
}



void citeste() {
    f >> n >> k;

    f.get();
    f.get(s, 3500000);
    int l = strlen(s), nr = 0, x = 0, semn = 1;
    for (int i = 0; i < l; i++) {
        if(s[i] == '-') semn = -1, i++;
        if (isdigit(s[i])) {
            while (isdigit(s[i])) {
                x = x * 10 + s[i] - '0';
                i++;
            }
            v[++nr] = x * semn;
            semn = 1; x = 0;
        }
    }
}

int main() {
    citeste();
    rezolva();
    return 0;
}