Cod sursa(job #290808)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 28 martie 2009 19:27:08
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<algorithm>
using namespace std;

#define DIM 500001
#define INF -1000001

int n,k,a[DIM],q[DIM];

void read(){
	int i,m,lg,nr,semn;
	char s[3*DIM];

	scanf("%d%d\n",&n,&k);
	gets(s);
	lg=strlen(s);
	for(i=m=0,semn=1; i<lg; ++i)
		if(s[i]=='-')
			semn=-1;
		else if(isdigit(s[i])){
			for(nr=0; isdigit(s[i]); nr=nr*10+s[i]-'0',++i);
			a[++m]=nr*semn;
            semn=1;}}

void solve(){
    int i,st,dr,poz,sol;

    for(i=st=1,dr=0; i<k; ++i){
        for(; dr>=st&&a[i]<=a[q[dr]]; --dr);
        q[++dr]=i;}
    for(i=k,sol=INF; i<=n; ++i){
        for(; st<=dr&&a[i]<=a[q[dr]]; --dr);
        q[++dr]=i;
        for(; st<=dr&&q[st]<i-k+1; ++st);
        if(a[q[st]]>sol){
            sol=a[q[st]];
            poz=i;}}
    printf("%d %d %d",poz-k+1,poz,sol);}

int main(){

    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    read();
    solve();
    return 0;}