Cod sursa(job #2472379)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 12 octombrie 2019 12:01:17
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#define MAXSIZE 500500
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

class deq
{
private:
    int a[MAXSIZE];
    int st, dr;
public:
    deq()
    {
        st = 0;
        dr = 0;
    }
    void popFront()
    {
        st++;
    }
    void popBack()
    {
        dr--;
    }
    void pushBack(int x)
    {
        a[dr] = x;
        dr++;
    }
    void pushFront(int x)
    {
        st--;
        a[st] = x;
    }
    bool isEmpty()
    {
        return st == dr;
    }
    int front()
    {
        return a[st];
    }
    int back()
    {
        return a[dr-1];
    }
};

int n, k;
deq myDeque;
int maxim = -30000, startMax, endMax;
int b[MAXSIZE];

void read()
{
    f>>n>>k;
    for(int i = 0; i<n; ++i)
        f>>b[i];
}

void addElement(int pos)
{
    while(!myDeque.isEmpty() && b[myDeque.back()] >= b[pos])
    {
        myDeque.popBack();
    }
    myDeque.pushBack(pos);
}

void deleteLast(int pos)
{
    while(pos - myDeque.front() >= k)
        myDeque.popFront();
}

void solve()
{
    for(int i = 0; i<k-1; ++i)
    {
        addElement(i);
    }
    for(int i = k-1; i<n; ++i)
    {
        addElement(i);
        deleteLast(i);
        int baza = b[myDeque.front()];
        if(baza > maxim)
        {
            maxim = baza;
            startMax = i-k+1;
            endMax = i;
        }
    }
    g<<startMax+1<<" "<<endMax+1<<" "<<maxim;
}

int main()
{
    ios::sync_with_stdio(false);
    read();
    solve();
    return 0;
}