Cod sursa(job #2891452)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 18 aprilie 2022 18:35:51
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <deque>
#include <stdio.h>
#include <inttypes.h>

#define NMAX 500001
#define MAX 30001

using namespace std;

#include <stdio.h>
#include <ctype.h>
 
/** Funcţiile necesare parsării fişierului de intrare **/
FILE *_fin;
int _in_loc; char _in_buff[4096];
 
 
void read_init(const char* nume) // Apelaţi această funcţie la începutul funcţiei <main>
{
	_fin = fopen(nume, "r");
	_in_loc = 4095;
}
 
char read_ch()
{
	++_in_loc;
	if (_in_loc == 4096) {
		_in_loc = 0;
		fread(_in_buff, 1, 4096, _fin);
	}
	return _in_buff[_in_loc];
}
 
int read_u32() // Apelaţi această funcţie pentru a citi un număr ce se încadrează în categoria <unsigned int>
{
	int u32 = 0; char c;
	while (!isdigit(c = read_ch()) && c != '-');
	int sgn = 1;
	if (c == '-') {
		sgn = -1;
	} else {
		u32 = c - '0';
	}
	while (isdigit(c = read_ch())) {
		u32 = u32 * 10 + c - '0';
	}
	return u32 * sgn;
}

int v[NMAX];

int main()
{
	read_init("secventa.in");
	int n, k;
	n = read_u32();
	k = read_u32();

	deque <int> dq;
	for (int i = 1; i <= k; ++i) {
		v[i] = read_u32();
		while (!dq.empty() && v[dq.back()] >= v[i])
			dq.pop_back();
		dq.push_back(i);
	}

	int best = v[dq.front()];
	int best_start = 1;
	int best_end = k;

	for (int i = k + 1; i <= n; ++i) {
		v[i] = read_u32();
		while (!dq.empty() && v[dq.back()] >= v[i])
			dq.pop_back();
		dq.push_back(i);
		if (i - dq.front() + 1 > k)
			dq.pop_front();
		int dq_fr = dq.front();
		if (best < v[dq_fr]) {
			best = v[dq_fr];
			best_start = i - k + 1;
			best_end = i;
		}
	}

	while (best_start >= 2 && v[best_start - 1] >= best)
		--best_start;

	FILE *out = fopen("secventa.out", "wt");

	fprintf(out, "%d %d %d\n", best_start, best_end, best);

	return 0;
}