Cod sursa(job #358645)

Utilizator vladiiIonescu Vlad vladii Data 23 octombrie 2009 22:25:43
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
int main() {
    deque<pair <int, int> > deq;
    fstream f1, f2;
    f1.open("secventa.in", ios::in);
    int n, k, mat, i, max=-30001, start;
    f1>>n>>k;
    for(i=1; i<=k; i++) {
             f1>>mat;
             while(!deq.empty() && mat<=deq.back().first) {
                              deq.pop_back();
             }
             deq.push_back(make_pair(mat, i));
    }
    start=1;
    for(i=k+1; i<=n; i++) {
               f1>>mat;
               /**
               while(!deq.empty() && deq.front().second<=i-k) {
                             deq.pop_front();
               }
               **/
               if(deq.front().first>max) { max=deq.front().first; start=deq.front().second; }
               if(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)); 
    }
    if(deq.front().first>max) { max=deq.front().first; start=n-k+1; }
    f2.open("secventa.out", ios::out);
    f2<<start<<" "<<start+k-1<<" "<<max;
    f1.close(); f2.close();          
    return 0;
}