Cod sursa(job #1371726)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 4 martie 2015 00:42:29
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define inFile "secventa.in"
#define outFile "secventa.out"
#define MAX_N 500001
#define INF 1<<30

int a[MAX_N], left[MAX_N], right[MAX_N], s[MAX_N];

int main() {
    FILE *in = fopen(inFile, "r");
    FILE *out = fopen(outFile, "w");
    
    int n, k;
    register int i, lev;
    
    fscanf(in, "%d %d", &n, &k);
    for(i = 1; i <= n; i++)
        fscanf(in, "%d", &a[i]);
        
    for(i = 1, lev = 1; i <= n; i++) {
        while(lev > 1 && a[i] < a[s[lev-1]])
            right[s[lev-1]] = i, lev--;
        s[lev++] = i;
    }
    while(lev > 1)
        right[s[lev-1]] = n+1, lev--;
    
    for(i = n, lev = 1; i; i--) {
        while(lev > 1 && a[i] < a[s[lev-1]])
            left[s[lev-1]] = i, lev--;
        s[lev++] = i;
    }
    while(lev > 1)
        left[s[lev-1]] = 0, lev--;
        
    int base_max = -INF, i_max = -1, j_max = -1;
    for(i = 1; i <= n; i++) {
        if(right[i] - left[i] - 1 >= k) {
            if(a[i] > base_max) {
                base_max = a[i];
                i_max = left[i]+1;
                j_max = max(i, left[i]+k);
            }
        }
    }
    
    fprintf(out, "%d %d %d\n", i_max, j_max, base_max);
    
    return 0;
}