Cod sursa(job #2731342)

Utilizator VladPislaruPislaru Vlad Rares VladPislaru Data 27 martie 2021 18:05:45
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("secventa.in");
ofstream fout ("secventa.out");

priority_queue <int , vector <int> , greater <int> > q;
int n , k , a[500005],fr[60005];
char s[3800000];

int main()
{
    int i, p1 , p2 , bmax = 0,semn = 0 , x, j = 0;
    fin >> n >> k;
    fin.get();
    fin.getline(s,3800000);
    for (i = 0; s[i]; )
    {
        if (s[i] == ' ') i++;
        else if (s[i] == '-')
        {
            semn = 1;
            i++;
        }
        else if (isdigit(s[i]))
        {
            x = 0;
            while (isdigit(s[i]))
            {
                x = x * 10 + s[i] - '0';
                i++;
            }
            if (semn == 1)
                a[++j] = -x;
            else a[++j] = x;
            semn = 0;
        }
    }
    for (i = 1; i <= k; i++)
    {
        q.push (a[i]);
        fr[a[i] + 30000]++;
    }
    p1 = 1;
    p2 = k;
    bmax = q.top();
    for (i = k + 1; i <= n; i++)
    {
        fr[a[i - k] + 30000]--;
        while (fr[q.top() + 30000] == 0)
            q.pop();
        q.push(a[i]);
        fr[a[i] + 30000]++;
        if (bmax < q.top())
        {
            bmax = q.top();
            p1 = i - k + 1;
            p2 = i;
        }
    }
    fout << p1 << " " << p2 << " " << bmax << "\n";
    return 0;
}