Cod sursa(job #812418)

Utilizator IoannaPandele Ioana Ioanna Data 13 noiembrie 2012 20:49:58
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
#include<vector>

using namespace std;

int n,k;
int maxim;

vector <int> deq;
vector <int> poz;

ifstream in("secventa.in");
ofstream out("secventa.out");

void scan()
{
    in>>n>>k;
}

void deque()
{
    int i,a,w=0;
    int st,dr,inc,sf;
    st=0;
    dr=-1;
    for (i=1;i<=n;i++)
    {
        in>>a;
        while (dr>=st && deq[dr]>a)
        {
            dr--;
        }
        dr++;
        if (dr==deq.size())
        {
            deq.push_back(a);
            poz.push_back(i);
        }
        else
        {
            deq[dr]=a;
            poz[dr]=i;
        }
        if (poz[st]==i-k)
            st++;
        if (i>=k)
        {
            if (!w)
            {
                maxim=deq[st];
                inc=poz[st];
                sf=i;
                w=1;
            }
            else
            if (maxim<deq[st])
            {

                inc=poz[st];
                sf=i;
                maxim=deq[st];
            }
        }
        }
    out<<inc<<" "<<sf<<" "<<maxim<<"\n";
}
int main()
{
    scan();
    deque();
    return 0;
}