Cod sursa(job #2472065)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 11 octombrie 2019 23:13:48
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
deque <int> minQ;
vector <int> a;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int main()
{
    ios_base::sync_with_stdio(0);
    fin.tie(NULL);
    int n, k, maxi = -30001;
    fin >> n >> k;
    int poz1 = n, poz2 = n;
    a.resize(n);
    for(int i = 0; i < n; ++i)
        fin >> a[i];
    for(int i = 0; i < n; ++i)
    {
        while (!minQ.empty() && a[minQ.back()] > a[i])
            minQ.pop_back();
        minQ.push_back(i);
        if (i - minQ.front() >= k)
            minQ.pop_front();
        if(a[minQ.front()] > maxi && i >= k - 1)
        {
            maxi = a[minQ.front()];
            if(minQ.front() <= n - k)
            {
                poz1 = minQ.front();
                poz2 = poz1 + k - 1;
            }
            else
            {
                poz2 = minQ.front();
                poz1 = poz2 - k + 1;
            }
        }
    }
    fout << poz1 + 1 << " " << poz2 + 1 << " " << maxi << "\n";
    return 0;
}