Cod sursa(job #2707889)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 17 februarie 2021 21:41:50
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
 
using namespace std;
 
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 = n * 10 + c - '0';
        n *= sgn;
        return *this;
    }
};
 
InParser f("secventa.in");
ofstream g("secventa.out");
 
deque <pair <int, int>> Q;
int N, K, x, mx, pz1, pz2;
 
int main(){
 
	f >> N >> K;
	for(int i = 1;i <= K;i++){
		f >> x;
		while(!Q.empty() && Q.back().first > x)
			Q.pop_back();

		Q.emplace_back(x, i);
	}

	pz1 = 1, pz2 = K, mx = Q.front().first;
	for(int i = K + 1;i <= N;i++){
		f >> x;

		if(!Q.empty() && Q.front().second == i - K)
			Q.pop_front();
 
		while(!Q.empty() && Q.back().first > x)
			Q.pop_back();
 
		Q.emplace_back(x, i);
		if(Q.front().first > mx){
			mx = Q.front().first;
			pz1 = i - K + 1;
			pz2 = i;
		}
	}
 
	g << pz1 << " " << pz2 << " " << mx;
}