Cod sursa(job #2045962)

Utilizator trifangrobertRobert Trifan trifangrobert Data 23 octombrie 2017 10:18:01
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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 &x)
{
    for (; !('0' <= ch && ch <= '9'); Next);
    for (x = 0; '0' <= ch && ch <= '9'; x = x * 10 + (ch - '0'), Next);
}

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;
}