Cod sursa(job #2045977)

Utilizator trifangrobertRobert Trifan trifangrobert Data 23 octombrie 2017 10:42:06
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>

#include <fstream>
#include <deque>
#define limit 5010
#define ch (buffer[position])
#define Next (++position == limit) ? (fin.read(buffer, limit), position = 0) : 0

using namespace std;


ifstream fin("secventa.in");
int position  = 0;
char buffer[limit];
int n, k, Max = -30010, x;
int v[500010];
deque <int> d;

void Read(int &rez)
{
    bool isNegative = false;
    for (; !('0' <= ch && ch <= '9') && ch != '-' ; Next);
    for(rez = 0 ; ('0' <= ch && ch <= '9') || ch == '-' ; Next)
    {
        if (ch == '-')
            isNegative = true;
        else if ('0' <= ch && ch <= '9')
            rez = rez * 10 + (ch - '0');
    }
    if (isNegative == true)
        rez = -rez;
}

void Read()
{
    //fin >> n >> k;
    Read(n);
    Read(k);
    for (int i = 1;i <= n;++i)
    {
        //fin >> v[i];
        Read(v[i]);
    }
    fin.close();
}

void Solve()
{
    for (int i = 1;i <= n;++i)
    {
        while(!d.empty() && v[d.back()] >= v[i])
            d.pop_back();
        d.push_back(i);
        if (i - k == d.front())
            d.pop_front();
        if (i >= k)
        {
            if (Max < v[d.front()])
            {
                Max = v[d.front()];
                x = i;
            }
        }
    }
}

void Write()
{
    ofstream fout("secventa.out");
    fout << x - k + 1 << " " << x << " " << Max << "\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}