Cod sursa(job #130263)

Utilizator hadesgamesTache Alexandru hadesgames Data 31 ianuarie 2008 18:30:14
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdio.h>    
#include <math.h>    
#include <string.h>    
#include <ctype.h>    
#define MAXN 500010    
long a[MAXN], n, k;    
char st[MAXN * 7];    
long deq[MAXN], start, final;    
      
   inline void insert(long value) {    
       while (final >= start && deq[final] > value) {    
           --final;    
       }    
       deq[++final] = value;    
   }    
       
   inline void del(long value) {    
       if (deq[start] == value) {    
           ++start;    
	}    
}    
	
int main() {    
       long i, na, p = 0, ok = 0, semn = 1, max = 0, poz_st = 0;    
       freopen("secventa.in", "r", stdin);    
       freopen("secventa.out", "w", stdout);    
       scanf("%ld %ld\n", &n, &k);    
       fgets(st, MAXN * 7, stdin);    
       na = 0;    
       for (i = 0; st[i] != 0; ++i) {    
           if (st[i] == '-') {    
               semn = -1;    
               continue;    
           }    
           if (isdigit(st[i])) {    
               p = p * 10 + (long)(st[i] - '0');    
               ok = 1;    
           } else {    
               a[++na] = p * semn;    
               p = 0;    
               semn = 1;    
              ok = 0;    
		}    
       }    
       if (ok) {    
		a[++na] = p;    
		p = 0;    
	}    
		
//deque    
	for (i = 1; i <= k; ++i) {    
		insert(a[i]);    
	}    
	max = deq[start];    
	poz_st = 1;    
	
	for (i = k + 1; i <= n; ++i) {    
		del(a[i - k]);    
		insert(a[i]);    
		 if (max < deq[start]) {    
			max = deq[start];    
			poz_st = i - k + 1;    
		}    
	}    
	printf("%ld %ld %ld\n", poz_st, poz_st + k - 1, max);    
	return 0;    
   }