Cod sursa(job #2499165)

Utilizator tomaionutIDorando tomaionut Data 25 noiembrie 2019 16:28:33
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;

char s[4000000];
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int a[500005], n, k;
deque<int> q;

int main()
{
    int i, semn = 1, x, m = 0, M, dr;
    fin >> n >> k;
    fin.get();
    fin.getline(s, 3999999);
    for (i = 0; s[i]; )
        if (s[i] == ' ') i++;
        else if (s[i] == '-') {semn = -1; i++;}
        else /// este cifra!
        {
            x = 0;
            while ('0' <= s[i] && s[i] <= '9')
            {
                x = x * 10 + (s[i] - '0');
                i++;
            }
            a[++m] = semn * x;
            semn = 1;
        }
    /// primele k elemente in deque
    for (i = 1; i <= k; i++)
    {
        x = a[i];
        /// scot din q elementele >= x
        while (!q.empty() && a[q.back()] >= x)
            q.pop_back();
        q.push_back(i);
    }
    M = a[q.front()];
    dr = k;
    for (i = k + 1; i <= n; i++)
    {
        x = a[i];
        /// scot din q elementele >= x
        while (!q.empty() && a[q.back()] >= x)
            q.pop_back();
        q.push_back(i);
        if (q.front() <= i - k) q.pop_front();
        if (M < a[q.front()])
        {
            M = a[q.front()];
            dr = i;
        }
    }
    fout << dr - k + 1 << " " << dr << " " << M << "\n";
    fout.close();
    return 0;
}