Cod sursa(job #1218422)

Utilizator andreey_047Andrei Maxim andreey_047 Data 10 august 2014 23:36:24
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#define nmax 500009
using namespace std;
int n,k;
typedef int Deque;
Deque D[nmax];
int a[nmax],maxim;
int main(){
    int i,front,back,x,sum=0,j,pi,pf=0,aux,q;
   ifstream fin("secventa.in");
    fin >> n >> k;
    front = 1; back = 0;
    for(i=1;i<=n;i++) fin >> a[i];
    fin.close();
    maxim = -99999; pi = 1;
    for(i=1;i<=n;i++){
        while(front <= back && a[i] < a[D[back]]) back--;
    D[++back] = i;

    if(a[D[front]] < a[i] && D[front] <= i-k) {front++;}
    if(i >= k && a[D[front]] > maxim) {pi = D[front];  maxim = a[D[front]];}
    }
    q = pi; aux = pi;
    while(a[q] >= maxim && q > 0) q--;
    q++;
    if(pi - q >= k) pf = pi;
    else pf = pi + k-(pi-q)-1;
    ofstream fout("secventa.out");
   fout << q<<' '<<pf<<' '<<maxim<<'\n';
   fout.close();
    return 0;
}