Cod sursa(job #1898246)

Utilizator FrequeAlex Iordachescu Freque Data 1 martie 2017 21:41:31
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <deque>

using namespace std;

FILE *f = fopen("secvente.in", "r");
ofstream fout("secvente.out");

struct minim
{
    int val;
    int st;
    int dr;
};

const int NMAX = 5000000 + 5;

deque <int> dq;

minim minn;

int n, k, K;
long long int sum;
int v[NMAX];

void read()
{
    fscanf(f, "%d%d", &n, &k);
    for (int i = 1; i <= n; ++i)
        fscanf(f, "%d", &v[i]);
    minn.val = -999999;
}

int main()
{
    read();
    for (int i = 1; i <= n; ++i)
    {
        //scoti de la inceput cat e nevoie
        //scoti de la sfarsit a.i sa fie cresc
        //add
        //verif daca i >= k
        while (!dq.empty() && dq.front() < i - k + 1)
            dq.pop_front();

        while (!dq.empty() && v[dq.back()] > v[i])
            dq.pop_back();

        dq.push_back(i);

        if (i >= k && minn.val < v[dq.front()])
        {
            minn.val = v[dq.front()];
            minn.st = i - k + 1;
            minn.dr = i;
        }
    }
    fout << minn.st << " " << minn.dr << " " << minn.val << '\n';
    return 0;
}