Cod sursa(job #2267497)

Utilizator ArsuhArsene Vlad Arsuh Data 23 octombrie 2018 18:32:44
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <fstream>
#include <deque>

using namespace std;

deque<pair<int, int>> deck;
int n, k;

/*void save(int& prim, int& ultim, int& nr)
{
    int mini=500001, maxi=0;
    for(auto x:deck)
    {
        if(x.second>maxi)
            maxi=x.second;
        if(x.second<mini)
            mini=x.second;
    }
    nr=deck.front().first;
    prim=mini;
    ultim=maxi;
}

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

    int x;
    f>>n>>k>>x;
    deck.push_back({x,1});
    int prim=1, ultim=1, nr=x;

    for(int i=2; i<=n; i++)
    {
        f>>x;
        if(deck.empty() || x>=deck.back().first)
            deck.push_back({x,i});
        else if(x>deck.front().first)
            if(i<=n-k+1)
            {
                deck.pop_front();
                deck.push_front({x,i});
            }
            else
            {
                deck.push_back({x,i});
                if(i==n && deck.size()>=k && deck.front().first > nr)
                    save(prim, ultim, nr);
            }
        else if(x==deck.front().first)
            deck.push_front({x,i});
        else
        {
            if(deck.size()>=k && deck.front().first > nr)
                save(prim, ultim, nr);
            deck.clear();
        }
    }

    cout<<prim<<' '<<ultim<<' '<<nr;
}*/

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

    int x;
    f >> n >> k >> x;
    deck.push_back({x, 1});

    int nr = x, prim, ultim;

    for (int i = 2; i <= n; i++)
    {
        f >> x;

        if (!deck.empty())
        {
            if (x > deck.back().first)
                deck.push_back({x, i});
            else
            {
                while (!deck.empty() && x <= deck.back().first)
                    deck.pop_back();
                deck.push_back({x, i});
            }
        }
        else
            deck.push_back({x, i});

        if (i-k >= deck.front().second)
            deck.pop_front();

        if (i >= k)
            if (deck.front().first > nr)
            {
                nr = deck.front().first;
                ultim = i;
                prim = i - k + 1;
            }
    }

    g << prim << ' ' << ultim << ' ' << nr;
}

int main()
{
    rez();
    return 0;
}