Cod sursa(job #1257744)

Utilizator bullseYeIacob Sergiu bullseYe Data 8 noiembrie 2014 10:04:00
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
//dq.push_front(val)
//dq.push_back(val)
//dq.back()
//dq.front()
//ultimele 2 returneaza primul element din dq sau ultimul
#include <cstdio>
#include <deque>
#define DMAX 5000010
using namespace std;

void citire();
void afisare();
void rez();

deque <int> dq;
int n, k, a[DMAX];
int ic, sc;
int sol=0;

int main()
{
    citire();
    rez();
    afisare();
    return 0;
}

void citire()
{
    FILE*fin=fopen ("secventa.in", "r");
    fscanf(fin, "%d %d", &n, &k);
    int i;
    for (i=1; i<=n; ++i)
        fscanf(fin, "%d", &a[i]);
    fclose(fin);
    return;
}

void rez()
{
    int i;//in dq avem pozitiile din vector
    for (i=1; i<=n; ++i)
    {
        if (!dq.empty() && dq.front()==i-k)//am trecut cu stanga secventei de pozitia dq.front()
            dq.pop_front();
        while (!dq.empty() && a[dq.back()]>=a[i])
                dq.pop_back();
        dq.push_back (i);
        if (i>=k && a[dq.front()]>sol)
        {
            ic=i-k+1;
            sc=i;
            sol=a[dq.front()];
        }
    }
    return;
}

void afisare()
{
    FILE*fout=fopen ("secventa.out", "w");
    fprintf(fout, "%d %d %d\n", ic, sc, sol);
    fclose(fout);
    return;
}