Cod sursa(job #358591)

Utilizator vladiiIonescu Vlad vladii Data 23 octombrie 2009 20:53:05
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
int main() {
    deque<pair <int, int> > deq;
    fstream f1, f2;
    int n, k, mat[500000], i, j, max, min, p, start;
    f1.open("secventa.in", ios::in);
    f1>>n>>k>>mat[1];
    deq.push_back(make_pair(mat[1], 1));
    for(i=2; i<=k; i++) {
             f1>>mat[i];
             p=deq.back().first;
             while(!deq.empty() && mat[i]<=p) {
                              deq.pop_back();
                              p=deq.back().first;
             }
             deq.push_back(make_pair(mat[i], i));
    }
    min=deq.front().first; start=1;
    max=min;
    for(i=k+1; i<=n; i++) {
               f1>>mat[i];
               p=deq.front().second;
               while(!deq.empty() && p<=i-k) {
                             deq.pop_front();
                             p=deq.front().second;
               }
               p=deq.back().first;
               while(!deq.empty() && mat[i]<=p) {
                              deq.pop_back();
                              p=deq.back().first;
               }
               deq.push_back(make_pair(mat[i], i)); 
               min=deq.front().first;
               if(min>max) { max=min; start=deq.front().second; }
    }
    f1.close();
    f2.open("secventa.out", ios::out);
    f2<<start<<" "<<start+k-1<<" "<<max;
    f2.close();               
    return 0;
}