Cod sursa(job #2191707)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 3 aprilie 2018 15:20:08
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#include <cstring>
#include <deque>
#define NMax 500002
#define NULL 0
using namespace std;
deque <int> MinS, MinP;
int N, i, K, drmin, minx, NR[NMax], signstring;
char WT[10000001], *p;
int main()
{

	FILE *fin = fopen("secventa.in", "r");
	FILE *fout = fopen("secventa.out", "w");
	fscanf(fin, "%d%d", &N, &K);
	fgetc(fin);
	fgets(WT, 10000001, fin);
	p = strtok(WT, " ");
	for (i = 1; i <= K; i++) {
		if (p[0] == '-') {
			signstring = -1; p += 1;
		}
		else signstring = 1;
		while (strlen(p)) {
			NR[i] = NR[i] * 10 + (p[0] - '0');
			p += 1;
		}
		NR[i] *= signstring;
		while (!MinS.empty() && NR[i] < MinS.back()) {
			MinS.pop_back();
			MinP.pop_back();
		}
		MinS.push_back(NR[i]);
		MinP.push_back(i + 1);
		p = strtok(NULL, " ");
	}
	minx = MinS.front();
	drmin = K;
	for(i=K+1; i<=N; i++){
		if (p[0] == '-') {
			signstring = -1; p += 1;
		}
		else signstring = 1;
		while (strlen(p)) {
			NR[i] = NR[i] * 10 + (p[0] - '0');
			p += 1;
		}
		NR[i] *= signstring;
		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();
		}
		p = strtok(NULL, " ");
	}
	fprintf(fout, "%d%c%d%c%d", drmin - K + 1, ' ', drmin, ' ', minx);
    return 0;
}