Cod sursa(job #1064491)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 21 decembrie 2013 22:34:02
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<cstdio>
#include<deque>
#include<climits>
#include<utility>
#include<vector>

using namespace std ;
 
int N, posm, MAX = INT_MIN, K ;
vector <pair <int, int> > V(500001) ;
 
int main() {
    int i, x, j, k ;
    freopen("secventa.in", "r", stdin) ;
    freopen("secventa.out", "w", stdout) ;
    scanf("%d %d", &N, &K) ;
    scanf("%d", &x) ;
    j = 1 ;
    V[j] = make_pair(x, 1) ;
    for (i = 2; i <= K; ++i) {
            scanf("%d", &x) ;
            while(j && x <= V[j].first) {
                --j;
            }
            ++j ;
            V[j] = make_pair(x, i) ;
    }
    MAX = V[j].first ;
    posm = K ;
    k = j ;
    j = 1 ;
    for (i = K + 1; i <= N; ++i) {
        //printf("%d %d\n", dq.front().first, dq.front().second) ;
        if (V[j].second == i - K) {
            ++j;
        }
        scanf("%d", &x) ;
        while(k >= j && x <= V[k].first) {
			--k;
        }
        ++k ;
        V[k] = make_pair(x, i) ;
        //printf("%d %d\n", dq.front().first, dq.front().second) ;
        if (V[j].first > MAX) {
            MAX = V[j].first ;
            posm = i ;
        }
    }
    printf("%d %d %d", posm - K + 1, posm, MAX) ;
    return 0 ;
}