Cod sursa(job #1224201)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 30 august 2014 01:45:21
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <deque>
#include <cstring>
using namespace std;

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

int n, k;
int A[nmax];

int i = 0, x = 0, j = 0, Max = -30001, hi, lo;
string s;
bool ok;

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 A[i] = A[i] * 10 + int(s[j]) - 48, j++;
                
        }
        
        if (ok) A[i] = -A[i];
        
        j++;
    }
    
    for (i = 1; i <= n; i++) {
        
        while (!deq.empty() && A[deq.back()] > A[i]) deq.pop_back();
        
        deq.push_back(i);
        
        if (deq.front() < i - k + 1 && i >= k) deq.pop_front();
        
        if (i >= k && A[deq.front()] > Max)
            Max = A[deq.front()],
            lo = i - k + 1,
            hi = i;
        
    }
    
    out << lo << " " << hi << " " << Max << "\n";
    
    return 0;
}