Cod sursa(job #818965)

Utilizator IoannaPandele Ioana Ioanna Data 18 noiembrie 2012 13:15:02
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#include<vector>
#define lim (1<<13)
#define check ++p==lim ? in.read(ch,lim),p=0 : 0
using namespace std;

int n,k,p;
int maxim;

char ch[lim+1];
vector <int> deq;
vector <int> poz;

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


inline void scan ( int &a )
{
    int semn=1;
    if (ch[0] == '\0')
        in.read (ch, lim) ;
    else for (; ch[p] < '0' || ch[p] > '9' ; check)
                if (ch[p]=='-')
                    semn=-1;
    for (a = 0 ; ch[p] >= '0' && ch[p] <= '9' ; a = a * 10 + ch[p] - '0', check) ;
    a=a*semn;
}

void deque()
{
    int i,a,w=0;
    int st,dr,inc,sf;
    st=0;
    dr=-1;
    maxim=-30001;
    for (i=1;i<=n;i++)
    {
        scan(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 (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(n);
    scan(k);
    deque();
    return 0;
}