Cod sursa(job #1794490)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 1 noiembrie 2016 12:48:24
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <cstring>
#include <climits>

using namespace std;

unsigned int N, K;
char s[3100000];

int a[500001], dq[500001];
short int sign;
unsigned int i, j, l, fr, bk, w, ct;

unsigned int lt, rt;
int sol;

int main ()
{
    ifstream fin ("secventa.in");
    fin >> N >> K;
    fin.get();
    fin.getline(s,3099999);
    fin.close();
    l = strlen(s);
    sol = INT_MIN;
    for (i=0; i<l; )
    {
        sign = 1;
        ct = 0;
        if (s[i] == '-')
        {
            sign = -1;
            i++;
        }
        while (s[i] >= '0' && s[i] <= '9')
        {
            ct = ct*10 + s[i] - '0';
            i++;
        }
        while (s[i] == ' ')
            i++;
        a[++w] = ct*sign;
    }
    fr = 1;
    for (i=1; i<=N; i++)
    {
        while (fr <= bk && a[dq[bk]] >= a[i])
            bk--;
        dq[++bk] = i;
        if (dq[bk]-dq[fr] == K)
            fr++;
        if (a[dq[fr]] > sol && dq[bk] >= K)
        {
            sol = a[dq[fr]];
            lt = dq[bk] - K + 1;
            rt = dq[bk];
        }
    }
    ofstream fout ("secventa.out");
    fout << lt << ' ' << rt << ' ' << sol;
    fout.close();
    return 0;
}