Cod sursa(job #2573941)

Utilizator LazarRazvanLazar Razvan LazarRazvan Data 5 martie 2020 19:32:40
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.29 kb
/*#include <iostream>
#include <fstream>
#include <queue>

#define INF 999999
#define MINF -999999

using namespace std;

typedef struct sequence
{
    int n = 0;
    deque < int > numbers;
    int base = INF;
}seq;

typedef struct result
{
    int start = 0;
    int finish = 0;
    int base = MINF;
}res;

ifstream fin;
ofstream fout;

int n, k;

seq readFirstSequence()
{
    seq sequence;

    sequence.n = k;

    for (int i = 1; i <= k; i++)
    {
        int nr;
        fin >> nr;

        sequence.numbers.push_back(nr);

        if (nr < sequence.base)
            sequence.base = nr;
    }

    return sequence;
}

void insertNrInSeq(int number, seq &seq)
{
    seq.numbers.push_back(number);

    if (number < seq.base)
        seq.base = number;
}

void writeSeq(seq seq)
{
    while(seq.n > 0)
    {
        seq.n--;
        cout << seq.numbers.front() << " ";
        seq.numbers.pop_front();
    }

    cout << '\n';
}

int findBase(seq seq)
{
    int base = INF;

    while(seq.n > 0)
    {
        seq.n--;

        if (seq.numbers.front() < base)
            base = seq.numbers.front();

        seq.numbers.pop_front();
    }

    return base;
}

void updateResult(res &res, seq seq, int start, int finish)
{
    if (seq.base > res.base)
    {
        res.base = seq.base;
        res.start = start;
        res.finish = finish;
    }
}


int main() {

    fin.open("secventa.in");
    fout.open("secventa.out");

    fin >> n >> k;

    seq seq = readFirstSequence();
    res res;

    //writeSeq(seq);

    for (int i = k+1; i <= n; i++)
    {
        int number;
        fin >> number;

        seq.numbers.push_back(number);

        if (number <= seq.base) {

            seq.base = number;
            seq.numbers.pop_front();


        } else {
            if (seq.base == seq.numbers.front()) {
                seq.numbers.pop_front();
                seq.base = findBase(seq);
            } else
                seq.numbers.pop_front();

        }


        //writeSeq(seq);

        updateResult(res, seq, i-k+1, i);
        //cout << seq.base << '\n';

    }

    fout << res.start << " " << res.finish << " " << res.base;

    fin.close();
    fout.close();

    return 0;
}*/

#include <fstream>
#include <deque>
#include <string>

#define NMAX 500001

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");


deque < int > dq;
int n, k;
int v[NMAX];
string s;

int toNumber(int &index)
{
    while (s[index] == ' ')
        ++index;

    char sign = '+';

    if (s[index] == '-') {
        sign = '-';
        ++index;
    }

    int nr = 0;

    while (s[index] >= '0' && s[index] <= '9') {

        nr = nr*10 + (s[index] -'0');

        ++index;
    }

    if (sign == '+')
        return nr;
    return -nr;
}

int main()
{
    fin >> n >> k;
    fin.get();
    getline(fin, s);

    int index = 0;
    int maximum = -30005, left, right;

    for (int i = 1; i <= n; i++)
    {
        v[i] = toNumber(index);

        while (!dq.empty() && v[i] <= v[dq.back()])
            dq.pop_back();

        dq.push_back(i);

        if (i - dq.front() + 1 > k)
            dq.pop_front();

        if (maximum < v[dq.front()] && i >= k)
        {
            maximum = v[dq.front()];
            right = i;
            left = i - k + 1;
        }
    }

    fout << left << ' ' << right << ' ' << maximum;
}