Cod sursa(job #812465)

Utilizator IoannaPandele Ioana Ioanna Data 13 noiembrie 2012 21:30:29
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<fstream>
#include<vector>

using namespace std;

int n,k;
int maxim;

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

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

void scan()
{
    char c;
    int a=0,sgn=1;
    in>>n>>k;
    in>>noskipws>>c;
    while (!in.eof())
    {
        in>>noskipws>>c;
        if (c==' ' || c=='\n')
        {
            a=a*sgn;
            v.push_back(a);
            a=0;
            sgn=1;
            continue;
        }
        if (c=='-')
        {
            sgn=-1;
            continue;
        }
        a=a*10+c-'0';
    }
}

void deque()
{
    int i,a,w=0;
    int st,dr,inc,sf;
    st=0;
    dr=-1;
    maxim=-30001;
    for (i=1;i<=n;i++)
    {
        a=v[i-1];
        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 (i-poz[st]+1>k)
            st++;
        if (i>=k)
        {
            if (maxim<deq[st])
            {

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