Cod sursa(job #1209517)

Utilizator clau_rClaudia clau_r Data 17 iulie 2014 22:08:19
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<iostream>
#include<fstream>
#include<deque>
#include<utility>
#include<algorithm>
#define NMAX 500010
using namespace std;


ifstream fin("secventa.in");
ofstream fout("secventa.out");
deque<pair<int, int> > d(2*NMAX);

int main(){
    int i;
    long int a, n, k;
    fin>>n>>k;
    
    int f, fi;
    fi = 1;
    fin>>a;
    d[0] = make_pair(a,0);
    for(i = 1; i< k; ++i){
        fin>>a;
		pair<int, int> p;
        p  = make_pair(a,i);
        f = fi -1;
        while (f>=0 && a< d[f].first) {
            //d[f+1] = d[f];
            f--;
        }
        d[f+1] = p;
        ++fi;
    }
   
    //fi = k;
    int init = 1;
    int bM = d[0].first;
    int bidx = 0;
    for(;i<n; i++){
        
        fin>>a;
        //f = fi-1;
		f = fi;
		while(f >= init && a <d[f].first){
        //while(f>=0 && a < d[f].first){
            //d[f+1] = d[f];
            f--;
        }
        d[f+1] = make_pair(a,i);
        ++fi;
        while (d[init].second < i - (k-1)) ++init;
        if(d[init].first > bM){
        bM = d[init].first;
        bidx = d[init].second;
        }
    }

       fout<<bidx + 1<<" "<<bidx + k<<" "<<bM;
}