Cod sursa(job #983171)

Utilizator danlexDan Alexandru danlex Data 10 august 2013 23:57:52
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
#define MAX  500002

int k, n, v[MAX], xbase = -1000000, xmin, xmax;
deque<int> dq;

void print(){
	cout << endl;
	cout << n << " " << k << endl;
	for(int i = 0; i < n; i ++){
		cout << v[i] << " "; 
	}
	cout << endl;
	cout << xmin << " " << xmax << " " << xbase << endl;
	cout << endl;
}

void read(){
	int ind, x, sign = +1;
	char sir[1024];
    ifstream fi("secventa.in");
    fi >> n;
	fi >> k;
	for (int i = 1; i <= n; i ++){
		fi >> sir; 
		x = ind = 0; 
		sign = 1;
		if(sir[ind] == '-') {
			sign = -1;
			ind ++;
		}
		for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
    		x = x*10+(sir[ind]-'0');
		v[i] = sign * x;
	}
    fi.close();
}

void write(){
    ofstream fo("secventa.out");
    fo << xmin << " " << xmax << " " << xbase;
    fo.close();

}

void compute(){
	for(int i = 1; i <= n; i ++){
		while(!dq.empty() && dq.front() < i - k + 1){
			dq.pop_front();
		}
		while(!dq.empty() && v[i] < v[dq.back()]){
			dq.pop_back();
		}

		dq.push_back(i);

		if(i > k - 1 && v[dq.front()] > xbase){
			xbase = v[dq.front()];
			xmin = i - k + 1;
			xmax = i;
		}
	} 
	//print();
}

int main(void){
    read();
    compute();
	write();
    return 0;
}