Cod sursa(job #358632)

Utilizator vladiiIonescu Vlad vladii Data 23 octombrie 2009 22:03:34
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int main() {
    deque<pair <long, long> > deq;
    FILE *f1=fopen("secventa.in", "r"), *f2=fopen("secventa.out", "w");
    long n, k, mat, i, max, min, start;
    fscanf(f1, "%ld%ld%ld", &n, &k, &mat);
    deq.push_back(make_pair(mat, 1));
    for(i=2; i<=k; i++) {
             fscanf(f1, "%ld", &mat);
             while(!deq.empty() && mat<=deq.back().first) {
                              deq.pop_back();
             }
             deq.push_back(make_pair(mat, i));
    }
    min=deq.front().first; start=1;
    max=min;
    for(i=k+1; i<=n; i++) {
               fscanf(f1, "%ld", &mat);
               while(!deq.empty() && deq.front().second<=i-k) {
                             deq.pop_front();
               }
               while(!deq.empty() && mat<=deq.back().first) {
                              deq.pop_back();
               }
               deq.push_back(make_pair(mat, i)); 
               min=deq.front().first;
               if(min>max) { max=min; start=deq.front().second; }
    }
    fprintf(f2, "%ld %ld %ld\n", start, start+k-1, max);
    fclose(f1); fclose(f2);            
    return 0;
}