Cod sursa(job #2545906)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 13 februarie 2020 17:41:32
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 5e5 + 1;

int a[NMAX];

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {

			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

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

int main()
{
    int N, K;
    fin >> N >> K;
    deque<int> dq;

    int start, stop;
    int bazaMax = -100000;

    for (int i = 1; i <= N; ++i) {
        fin >> a[i];
        while (!dq.empty() && a[i] <= a[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (dq.front() <= i - K) {
            dq.pop_front();
        }
        if (i >= K) {
            if (a[dq.front()] > bazaMax) {
                bazaMax = a[dq.front()];
                start = i - K + 1;
                stop = i;
            }
        }
    }

    fout << start << ' ' << stop << ' ' << bazaMax << '\n';
    return 0;
}