Cod sursa(job #2191643)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 3 aprilie 2018 11:37:21
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <cstring>
#include <deque>
#define NMax 500002
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
deque <int> MinS, MinP;
int N, i, K, drmin, minx, NR[NMax], signstring, actualnumberwearegonnause, vf;
char whyteachusaboutbasicreadingifthisismoreefficient[10000001];
int main()
{
	fin >> N >> K;
	fin.get();
	fin.getline(whyteachusaboutbasicreadingifthisismoreefficient, 10000001);
	signstring = 1;
	vf = 1;
	for (i = 0; i <= strlen(whyteachusaboutbasicreadingifthisismoreefficient+1); i++) {
		if(whyteachusaboutbasicreadingifthisismoreefficient[i]==' '){
			NR[vf++] = (actualnumberwearegonnause*signstring);
			actualnumberwearegonnause = 0;
			signstring = 1;
		}
		else if(whyteachusaboutbasicreadingifthisismoreefficient[i]=='-') signstring = -1;
		else actualnumberwearegonnause = actualnumberwearegonnause * 10 + (whyteachusaboutbasicreadingifthisismoreefficient[i] - '0');
		}
	NR[N] = actualnumberwearegonnause * signstring;
	for (i = 1; i <= K; i++) {
		while (!MinS.empty() && NR[i] < MinS.back()) {
			MinS.pop_back();
			MinP.pop_back();
		}
		MinS.push_back(NR[i]);
		MinP.push_back(i + 1);
	}
	minx = MinS.front();
	drmin = K;
	for(i=K+1; i<=N; i++){
		if ((i - MinP.front()) >= K) {
		MinS.pop_front();
		MinP.pop_front();
		}
		while (!MinS.empty() && (NR[i] < MinS.back())) {
			MinS.pop_back();
			MinP.pop_back();
		}
		MinS.push_back(NR[i]);
		MinP.push_back(i);
		if (MinS.front() > minx) {
			drmin = i;
			minx = MinS.front();
		}
	}
	fout << drmin - K + 1 << " " << drmin << " " << minx;
    return 0;
}