Cod sursa(job #1512442)

Utilizator Nevermore10Macovei Cosmin Nevermore10 Data 28 octombrie 2015 04:02:49
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <cstring>
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

int n,k,v[500001];
int max1=-30001,rasp;
char s[4000007];
deque <int> st;

void rezolv() {
	for(int i = 0; i < n; i++) {
		while(st.size() && i-st.front() >= k) {
			st.pop_front();
		}
		while(st.size() && v[st.back()] > v[i]) {
			st.pop_back();
		}
		st.push_back(i);
		if(i >= k) {
			if(v[st.front()] > max1) {
				max1 = v[st.front()];
				rasp=i;
			
			}
		}
	}
	
}

void citire() {
	f >> n >> k;
	f.get();
	f.getline(s,4000007,EOF);
	int capat = strlen(s) , inc = 0;
	for(int i = 0; i < n; i++) {
		int minus = 1,nr = 0;
		if(s[inc] == '-') {
			minus = -1;
			inc++;
		}
		while(isdigit(s[inc]) && inc < capat) {
			nr = nr*10 + (s[inc] - 48);
			inc++;
		}
		inc++;
		nr*=minus;
		v[i] = nr;
	}
}

int main() {
	citire();
	rezolv();
	g << rasp-k+2 << " " << rasp+1 << " " << max1;
	f.close();
	g.close();
	return 0; 
}