Cod sursa(job #2722934)

Utilizator DragosC1Dragos DragosC1 Data 13 martie 2021 13:21:56
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <deque>
#include <vector>
using namespace std;

int n, k;
int a[500001];
int Max, st, dr;

class InParser {
  private:
    vector<char> str;
    int ptr;
    ifstream fin;
 
    char getChar() {
        if (ptr == (int) str.size()) {
            fin.read(str.data(), str.size());
            ptr = 0;
        }
        return str[ptr++];
    }
 
    template<class T>
    T getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();
        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }
        T num = 0;
        while (isdigit(chr)) {
            num = num * 10 + chr - '0';
            chr = getChar();
        }
        return sgn * num;
    }
 
  public:
    InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
    ~InParser() { fin.close(); }
 
    template<class T>
    friend InParser& operator>>(InParser& in, T& num) {
        num = in.getInt<T>();
        return in;
    }
};

void read() {
	int i;
	InParser f("secventa.in");;
	f >> n >> k;
	for (i = 1; i <= n; i++) 
		f >> a[i];
}

deque<int> dq;

void solve() {
	int i;
	Max = -500005;
	st = 0, dr = 0;
	for (i = 1; i <= n; i++) {
		while (dq.size() > 0 && a[i] <= a[dq.back()])
			dq.pop_back();
		dq.push_back(i);
		while (dq.size() > 0 && dq.front() + k <= i) 
			dq.pop_front();
		if (i >= k)
			if (a[dq.front()] > Max) {
				Max = a[dq.front()];
				st = i - k + 1, dr = i;
			}
	}
}

void output() {
	ofstream g("secventa.out"); g.tie(0);
	g << st << ' ' << dr << ' ' <<  Max;
	g.close();
}

int main() {
	ios::sync_with_stdio(0);
	read();
	solve();
	output();
	return 0;
}