Cod sursa(job #1147929)

Utilizator denis_tdrdenis tdr denis_tdr Data 20 martie 2014 11:42:53
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <deque>
#define nMax 500001
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");
int n, k, bMax, a, b, v[nMax];
deque<int> deq;
char s[7 * nMax + 10];
void read(){
    f>>n>>k;
    f.get();
    f.get(s, 7 * nMax + 10);
    int i=1;
    n=1;
    int x=0;
    bool semn=true;
    int l=strlen(s);
    s[l++]=' ';
    s[l]='\0';
    for(int i=0;i<l;i++)
    {
        if(s[i]==' ')
        {
            if(x!=30001)
                x*=semn?1:-1, v[n++]=x, x=0, semn=true;
            x=0;
            continue;
        }
        if(s[i]=='-')
        {semn=false;continue;}
        if(s[i]>='0' && s[i]<='9')
            x*=10, x+=(s[i]-'0');
    }
}
int main(){
    read();
    //return 0;
    bMax=-30001;
    for(int i=1;i<=n;i++){
        while(deq.size() && v[deq.back()]>v[i])
            deq.pop_back();
        deq.push_back(i);
        if(deq.front()==i-k)
            deq.pop_front();
        if(i>=k && v[deq.front()]>bMax)
            bMax=v[deq.front()], a=i-k+1, b=i;
    }
    g<<a<<" "<<b<<" "<<bMax;
    cout<<a<<" "<<b<<" "<<bMax;
    return 0;
}