Cod sursa(job #856315)

Utilizator Theorytheo .c Theory Data 16 ianuarie 2013 11:37:02
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");


#define NMAX 500003

vector<int> a;
int N; int K;
deque <int> q;
int last , baza = 0;

void Read () {

    fin >> N >> K;
    for(int i = 1; i <= N; i++){
        int x; fin >>x ;
        a.push_back(x);
    }
}

void Solve() {

    for(int i = 0; i < K; i++){
        if(!q.empty() && a[i] <= a[q.back()]) q.pop_back();
        q.push_back(i);
    }

    for(int i = K ; i < N; i++){
        if(q.front() == i - K) q.pop_front();

        if(!q.empty() && a[i] <= a[q.back()]) q.pop_back();
        q.push_back(i);

        if(a[q.front()] > baza){
            baza = a[q.front()];
            last = q.back();
        }
    }

}


void Print(){
    fout << last - K + 2<<" "<<last + 1<< " "<< baza;
}


int main() {

    Read();

    Solve();

    Print();

    return 0;
}