Cod sursa(job #2217096)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 29 iunie 2018 01:17:17
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

class InParser {

    private:

        ifstream File;
        static const unsigned int buffSZ = (1 << 15);
        unsigned int buffPos;
        char buff[buffSZ];

        void _advance() {

            if (++buffPos == buffSZ) {

                buffPos = 0;
                File.read(buff, buffSZ);
            }
        }

    public:

        InParser(const char *FileName) {

            File.open(FileName);
            buffPos = buffSZ - 1;
        }

        InParser& operator >>(int &no) {

            int sgn = 1;
            while (!isdigit(buff[buffPos])) {

                if (buff[buffPos] == '-')
                    sgn = -1;
                _advance();
            }
            no = 0;
            while (isdigit(buff[buffPos])) {

                no = no * 10 + buff[buffPos] - '0';
                _advance();
            }
            no *= sgn;
            return *this;
        }
};

const int MAXN = 5e5;
const int MAXK = 5e5;

int n, k, nr;
deque<pair<int, int>> dq;
int maxim = -30001;
int st, dr;

int main() {
	InParser cin("secventa.in");
	freopen("secventa.out", "w", stdout);

	ios::sync_with_stdio(false);

	cin >> n >> k;

	for (int i = 1; i < k; ++ i) {
		cin >> nr;
		while (dq.size() && dq.back().first >= nr) dq.pop_back();
		dq.push_back({nr, i});
	}

	for (int i = k; i <= n; ++ i) {
		cin >> nr;
		while (dq.size() && dq.front().second <= i - k) dq.pop_front();
		while (dq.size() && dq.back().first >= nr) dq.pop_back();
		dq.push_back({nr, i});
		if (dq.front().first > maxim) {
			st = i - k + 1;
			dr = i;
			maxim = dq.front().first;
		}

	}

	cout << st << ' ' << dr << ' ' << maxim;


	return 0;
}