Cod sursa(job #1552150)

Utilizator Emy1337Micu Emerson Emy1337 Data 17 decembrie 2015 12:06:49
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <cstdio>
using namespace std;

ofstream fout("secventa.out");

const int MAXN = 500100;


int values[MAXN];
deque< int > d;
int miny=-10000000,miny2,poz;
void insert(int poz)
{
    while (!d.empty() && values[d.back()] > values[poz])
        d.pop_back();
    d.push_back(poz);

}

int get_min(int curIndex)
{
    while(!d.empty() && d.front() < curIndex)
        d.pop_front();
    return values[d.front()];
}

int n,k;
const int BUFFERSIZE = 100000;
char buffer[BUFFERSIZE];

int get_int() {
    static int p = BUFFERSIZE;
    while ((buffer[p] < '0' || buffer[p] > '9') && buffer[p] != '-') {
        ++p;
        if (p >= BUFFERSIZE) {
            fread(buffer, 1, BUFFERSIZE, stdin);
            p = 0;
        }
    }

    int negative = 1;
    int rez = 0;
    if (buffer[p] == '-') {
        negative = -1;
        ++p;
    }

    while (buffer[p] >= '0' && buffer[p] <= '9') {
        rez = rez * 10 + ((int)buffer[p] - (int)'0');
        ++p;
        if (p >= BUFFERSIZE) {
            fread(buffer, 1, BUFFERSIZE, stdin);
            p = 0;
        }
    }

    return rez * negative;
}

int main()
{
    freopen("secventa.out", "r", stdin);
    n = get_int();
    k = get_int();
    for (int i = 1; i <= n; ++i)
        values[i] = get_int();

    for (int i = 1; i <= k; ++i)
        insert(i);

    for (int i = k + 1; i <= n + 1; ++i)
    {
        miny2=get_min(i - k);
        if(miny < miny2)
        {
            miny= miny2;
            poz= i-k;
        }

        insert(i);
    }
    fout<<poz<<" "<<poz+k-1<<" "<<miny;
}