Cod sursa(job #2028817)

Utilizator victoreVictor Popa victore Data 28 septembrie 2017 18:20:08
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include<queue>
#include<cstring>

using namespace std;

typedef pair<int,int> ii;
deque <ii> q;

FILE *f1 = fopen("secventa.in","r");
FILE *f2 = fopen("secventa.out","w");

const int nmax=500005;
const int buffmax=100005;

int co;

char s[buffmax];

inline bool isnum(char ch)
{
    return (ch >= '0' && ch <= '9');
}

inline void citeste(int &nr)
{
    fread(s , 1 , buffmax , f1);

    int csf=1;

    for(;!isnum(s[co]);)
    {
        if(s[co] == '-')
            csf=-1;
        if(++co == buffmax)
        {
            fread(s , 1 , buffmax , f1);
            co=0;
        }
    }
    nr=0;

    for(;isnum(s[co]);)
    {
        nr = nr*10 + (s[co]-'0');
        if(++co == buffmax)
        {
            fread(s , 1 , buffmax , f1);
            co=0;
        }
    }

    nr*=csf;
}

int main()
{

    int n,i,k,l,lmax,x,baza,bazmax,a=1,b=1;

    citeste(n);
    citeste(k);

    for(i=1;i<=n;i++)
    {
        citeste(x);
        while(!q.empty()&&q.back().first>=x)
            q.pop_back();
        while(!q.empty()&&i-q.front().second+1>k)
            q.pop_front();
        q.push_back(ii(x,i));
        baza=q.front().first;
        if(i>=k)
        {
            if(baza>bazmax||i==k)
            {
                bazmax=baza;
                a=i-k+1;
                b=i;
            }
        }
    }
    fprintf(f2 ,"%d %d %d",a,b,bazmax);
}