Cod sursa(job #1218938)

Utilizator somuBanil Ardej somu Data 12 august 2014 22:32:04
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <cstring>
using namespace std;

#define nmax 500001
ifstream in("secventa.in");
ofstream out("secventa.out");

int N,K,i,St,Dr,Max = -30001,j=0;
int V[nmax];
bool ok;
string S;
deque <int> deq;

int main() {
    
    in >> N >> K;
    in.get();
    getline(in, S);
    
    S[S.size()] = ' ';
    
    for (i=1; i<=N; i++) {
        
        ok = false;
        
        while(S[j] != ' ' && j <= S.size()){
            
            if (S[j] == '-') ok = true, j++;
            else V[i] = V[i]*10 + (S[j] - '0'), j++;
            
        }
        
        if (ok) V[i]=-V[i];
        
        j++;
        
    }
    
    for (i=1; i<=N; i++) {
        
        while(!deq.empty() && V[deq.back()] > V[i]) deq.pop_back();
        
        deq.push_back(i);
        
        if (deq.front() < i - K + 1 && i >= K) deq.pop_front();
        
        if (V[deq.front()] > Max && i >= K){
            Max = V[deq.front()];
            
            St = i - K + 1,
            Dr = i;
        }
    
    }
    
    out << St << " " << Dr << " " << Max << "\n";
    
    return 0;
}