Cod sursa(job #1697412)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 1 mai 2016 22:28:32
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <cstdio>
#include <iostream>
#include <vector>
#include <deque>
#define NMAX 5000005
#define HMAX 100005
#define pb push_back
#define INF 0x3f3f3f3f

using namespace std;

typedef pair<int, int> pii;

//ifstream fin("secventa.in");

FILE* fin=fopen("secventa.in","r");
const unsigned maxb=30000192;
char buf[maxb];
unsigned ptr=maxb;

inline int getInt(){
    int nr=0,semn=1;

    while((buf[ptr]<'0'||'9'<buf[ptr])&&buf[ptr]!='-')
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
	if(buf[ptr]=='-') {
		semn=-1;
		++ptr;
	}
    while('0'<=buf[ptr]&&buf[ptr]<='9'){
        nr=nr*10+buf[ptr]-'0';
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    }
    return nr*semn;
}

ofstream fout("secventa.out");

int main() {
	int n,k,i,val,valmax,st,dr;

	n=getInt();
	k=getInt();

	deque<pii> dq;
	valmax=-INF;
	for(i=1;i<=n;++i) {
		val=getInt();
		while(!dq.empty() && dq.back().second>val) dq.pop_back();

		dq.push_back({i,val});

		if(dq.front().first<=i-k) dq.pop_front();
		if(i>=k) {
			if(dq.front().second > valmax) {
				valmax=dq.front().second;
				st=i-k+1;
				dr=i;
			}
		}
	}

	fout<<st<<' '<<dr<<' '<<valmax;

	return 0;
}