Cod sursa(job #1623642)

Utilizator razvandRazvan Dumitru razvand Data 1 martie 2016 20:46:06
Problema Submultimi Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <stdio.h>
#define MAX 2000003

using namespace std;

FILE *fin = fopen("secventa.in", "r");
FILE *fout = fopen("secventa.out", "w");
int v[500003];
deque<int> deq;
int n,k;
char s[MAX];
int kI = MAX;

char nextch() {
    if(kI == MAX) {
        fread(s, 1, MAX, fin);
        kI = 0;
    }
    return s[kI++];
}

int read() {
    char c = nextch();
    while(!isdigit(c) && c != '-')
        c = nextch();
    bool sign = false;
    if(c == '-') {
        sign = true;
        c = nextch();
    }
    int rez = 0;
    while(isdigit(c)) {
        rez = rez*10 + c - '0';
        c = nextch();
    }
    if(sign)
        return rez*(-1);
    else
        return rez;
}

void ins(int val) {
    while(!deq.empty() && v[val] < v[deq.back()])
        deq.pop_back();
    deq.push_back(val);
}

void rem(int val) {
    while(!deq.empty() && val-k >= deq.front())
        deq.pop_front();
}

int main() {

    n = read();
    k = read();

    int maxF = -100000000;
    int maxI = 0;
    int maxE = 0;

    for(int i = 1; i <= n; i++) {

        v[i] = read();
        ins(i);
        rem(i);

        if(i >= k) {
            if(v[deq.front()] > maxF) {
                maxF = v[deq.front()];
                maxI = i-k+1;
                maxE = i;
            }
        }

    }

    fprintf(fout, "%d %d %d", maxI, maxE, maxF);

    return 0;
}