Cod sursa(job #913037)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 13 martie 2013 08:13:46
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
using namespace std;
#define DIM 500002
#define INF 1<<20
 
int A[DIM], Deque[DIM];
int N, K, Bmin, Bpoz;
int i ,p ,u;
 
int main (){
     
    ifstream f1("secventa.in");
    ofstream f2("secventa.out");
     
    f1 >> N >> K;
    for (i=1; i<=N; i++) f1 >> A[i];
     
    p = 1; u = 0; Bmin = -INF;
    for (i=1; i<=N; i++){
        while (p <= u && A[i] <= A[Deque[u]])
            u--;
        Deque[++u] = i;
        if (Deque[p] == i-K)
            p++;
        if (i >= K && Bmin < A[Deque[p]]){
            Bmin = A[Deque[p]];
            Bpoz = i;       
        }
    }
     
    f2 << Bpoz-K+1 << " " << Bpoz << " " << Bmin;
     
    return 0;
}