Cod sursa(job #904696)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 4 martie 2013 19:25:08
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <deque>
#include <ctype.h>
#include <string.h>
using namespace std;

ifstream cin("secventa.in");
ofstream cout("secventa.out");
deque <int> dq;
char s[1005];
int nr, u, semn;
int n, k, a[500005], i, maxi=-((1<<31)-1), st, dr;
inline int max(int a, int b)
{
    if(a>b) return a;
    return b;
}
int main()
{
    cin>>n>>k;
    cin.getline(s, 100);
    cin.getline(s, 1000);
    i=0;
    for(;s[i];)
        {
            nr=0;
            semn=1;
            while(!isdigit(s[i]))
                ++i;
            if(s[i-1]=='-')
                semn=-1;
            while(isdigit(s[i]))
                nr=nr*10+(s[i]-'0'), ++i;
            a[++u]=nr*semn;
            while(isspace(s[i]))
                ++i;
        }
    for(i=1;i<=u;++i)
        cout<<a[i]<<" ";
    for(i=1;i<=n;++i)
        {
            while(!dq.empty() && a[dq.back()]>=a[i])
                dq.pop_back();
            dq.push_back(i);
            if(i>k && dq.front()==i-k)
                dq.pop_front();
            if(i>=k)
                if(maxi<a[dq.front()])
                    {
                        maxi=a[dq.front()];
                        st=i-k+1;
                        dr=i;
                    }
        }
    while(a[st-1]>=maxi && st>1)
        --st;
    cin.close();
    cout<<st<<" "<<dr<<" "<<maxi<<"\n";
    cout.close();
    return 0;
}