Cod sursa(job #1064497)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 21 decembrie 2013 22:50:35
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<cstdio>
#include<deque>
#include<climits>
#include<utility>
#include<string>
#include<cstring>
 
using namespace std ;
 
int N, posm, MAX = INT_MIN, K, lg ;
deque <pair <int, int> > dq ;
//string S ;
char S[3000000];

int next(char *S, int &pos) {
	int x = 0;
	while (pos < lg && !isdigit(S[pos])) ++pos ;
	while (pos <lg && isdigit(S[pos])) {
		x = x * 10 + (S[pos] - '0') ;
		++pos ;
	}
	return x;
}

int main() {
    int i, x, pos = 0 ;
    freopen("secventa.in", "r", stdin) ;
    freopen("secventa.out", "w", stdout) ;
	gets(S) ;
	lg = strlen(S) ;

	
//    scanf("%d %d", &N, &K) ;
	N = next(S, pos) ;
	//printf("%d\n", N) ; 
	K = next(S, pos) ;
	//printf("%d\n", K) ; 
	gets(S) ;
	lg = strlen(S) ; 
	pos = 0 ;
	x = next(S, pos) ;
	
    //scanf("%d", &x) ;
    dq.push_back(make_pair(x, 1)) ;
    for (i = 2; i <= K; ++i) {
            //scanf("%d", &x) ;
            x = next(S, pos) ;
            while(!dq.empty() && x <= dq.back().first) {
                dq.pop_back() ;
            }
            dq.push_back(make_pair(x, i)) ;
    }
    MAX = dq.front().first ;
    posm = K ;
    for (i = K + 1; i <= N; ++i) {
        //printf("%d %d\n", dq.front().first, dq.front().second) ;
        if (dq.front().second == i - K) {
            dq.pop_front() ;
        }
        //scanf("%d", &x) ;
        x = next(S, pos) ;
        while(!dq.empty() && x <= dq.back().first) {
            dq.pop_back() ;
        }
        dq.push_back(make_pair(x, i)) ;
        //printf("%d %d\n", dq.front().first, dq.front().second) ;
        if (dq.front().first > MAX) {
            MAX = dq.front().first ;
            posm = i ;
        }
    }
    printf("%d %d %d", posm - K + 1, posm, MAX) ;
    return 0 ;
}