Cod sursa(job #862862)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 22 ianuarie 2013 23:26:36
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<deque>
#define NMax 5000005
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");
deque <int> v;
char sir[3500000];
int a[NMax],sum;

int main ()
{
    int i,n,k,max=-30005,s1,s2,lg,semn,crt=0,nr;
    f>>n>>k;
    f.get();
    f.get(sir,3500000);
    lg=strlen(sir);
    for (i=0; i<lg; i++)
    {
        semn=1; nr=0;
        if (sir[i]=='-')
        {
            semn=-1;
            i++;
        }
        while (sir[i]>='0' && sir[i]<='9')
        {
            nr=nr*10+(sir[i]-'0');
            i++;
        }
        a[++crt]=semn*nr;
    }
    for (i=1; i<=n; i++)
    {
        while (!v.empty() && a[v.back()]>a[i])
            v.pop_back();
        v.push_back(i);
        if (v.front()==i-k)
            v.pop_front();
        if (i>=k && a[v.front()]>max)
        {
            max=a[v.front()];
            s1=i-k+1;
            s2=i;
        }
    }
    g<<s1<<" "<<s2<<" "<<max;
    return 0;
}