Cod sursa(job #474941)

Utilizator marius.bucurBucur Marius - Ovidiu marius.bucur Data 5 august 2010 16:11:16
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<deque>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<fstream>

using namespace std;

int N,K;
std::vector<int> vec;
deque<int> Q;

int main() {
	ifstream in("secventa.in");
	in >> N;
	in >> K;
	int smin = 0;
	int smin_index = 0;
	for(int i = 0; i < N; i++) {
		int aux;
		in >> aux;
		vec.push_back(aux);
	}
	for(int i = 0; i < N; i++) {
		if(i - Q.front() >= K) {
			Q.pop_front();
			//printf("[%d %d]\n", vec[Q.front()], smin);
		}
		while(!Q.empty() && vec[Q.back()] > vec[i])
			Q.pop_back();
		Q.push_back(i);
		if(i >= K-1)
		if(vec[Q.front()] > smin) {
			smin = vec[Q.front()];
			smin_index = i - K + 1;
		}
	}
	in.close();
	smin_index++;//o based array
	ofstream out("secventa.out");
	out << smin_index << " " << smin_index + K - 1 << " " << smin << "\n";
	out.close();
}