Cod sursa(job #2500726)

Utilizator NeganAlex Mihalcea Negan Data 28 noiembrie 2019 16:29:36
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>

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

char s[4000000];
int a[500005], n, k;
deque<int>q;
void Citire()
{
    int i, semn = 1, x;
    fin >> n >> k;
    fin.get();
    fin.getline(s, 3999999);
    n = 0;
    for(i = 0;s[i];)
        if(s[i] == ' ')
            i++;
        else
            if(s[i] == '-')
            {
                semn = -1;
                i++;
            }
        else
        {
            x = 0;
            while(s[i] <= '9' && s[i] >= '0')
            {
                x = x * 10 + s[i] - '0';
                i++;
            }
            a[++n] = semn * x;
            semn = 1;
        }
}
void Solve()
{
    int i, M, x, dr;
    for(i = 1;i <= k;i++)
    {
        x = a[i];
        ///scot din dreapta numerele >= 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 dreapta numerele >= 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();
}
int main()
{
    Citire();
    Solve();
    return 0;
}