Cod sursa(job #1675360)

Utilizator serbanSlincu Serban serban Data 5 aprilie 2016 11:50:15
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define pii pair<int, int>

using namespace std;

int a[500005];
int d[500005];
int l = 1, r, n, k;

FILE *f = fopen("secventa.in", "r");
ofstream g("secventa.out");

char s[700010];

void citire() {
    fgets(s, 700000, f);
    int o = 0, nr = 0, times = 1;
    int i = 0;
    while(o < 2) {
        if(s[i] == '-') times = -1;
        else if(isdigit(s[i])) {
            nr *= 10;
            nr += s[i] - '0';
        }
        else {
            o ++;
            a[o] = nr * times;
            nr = 0;
            times = 1;
        }
        i ++;
    }
    n = a[1]; k = a[2];
    o = 0;
    for(; o < n;) {
        if(s[i] == '-') times = -1;
        else if(isdigit(s[i])) {
            nr *= 10;
            nr += s[i] - '0';
        }
        else if(s[i] == ' ') {
            o ++;
            a[o] = nr * times;
            nr = 0;
            times = 1;
        }
        i ++;
        if(i == 700000) {
            fgets(s, 700000, f);
            i = 0;
        }
    }
}

int main()
{
    int x, st, dr, mx = -30005;
    citire();
    for(int i = 1; i < k; i ++) {
        while(l <= r && a[i] < a[d[r]]) r --;
        d[++ r] = i;
    }
    for(int i = k; i <= n; i ++) {
        while(l <= r && a[i] < a[d[r]]) r --;
        d[++ r] = i;
        if(i - k >= d[l]) l ++;
        if(mx < a[d[l]]) {
            mx = a[d[l]];
            dr = d[r];
            st = d[r] - k + 1;
        }
    }
    g << st << " " << dr << " " << mx << "\n";
    return 0;
}