Cod sursa(job #2305899)

Utilizator OctavianVasileVasileOctavian OctavianVasile Data 21 decembrie 2018 12:11:46
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <ctype.h>
FILE *_fin;
int _in_loc; char _in_buff [4096];
void read_init(const char* nume){
	_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 (){
	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;
}
#include <bits/stdc++.h>
using namespace std;
ofstream fout ("secventa.out");
#define MAXN 500003
int v [MAXN], N, K;
int p, ans = -1000000003;
deque <int> dq;
int main (){
    read_init ("secventa.in");
    N = read_u32 (); K = read_u32 ();
    for (int i = 1; i <= N; i ++)v [i] = read_u32 ();
    for (int i = 1; i <= N; i ++){
        while (!dq.empty () && v [i] < v [dq.back ()])
            dq.pop_back ();
        dq.push_back (i);
        if (dq.front () == i - K)dq.pop_front ();
        if (i - K >= 0 && ans < v [dq.front ()])
            ans = v [dq.front ()], p = dq.back ();
    }
    fout << p - K + 1 << " " << p << " " << ans;
    return 0;
}