Cod sursa(job #1224200)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 30 august 2014 01:39:14
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 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;

deque <int> deq;

int main() {
    
    in >> n >> k, in.get();
    getline(in, s);
    
    s[s.size()] = ' ';

    while (i <= s.size()) {
        
        if (s[i] == '-') {
            
            i++;
            
            while (s[i] != ' ')
                x = x * 10 + (int(s[i]) - 48), i++;
            
            A[++j] = -x;
            
            x = 0, i++;
            
        }
        
        while (s[i] != ' ')
            x = x * 10 + (int(s[i]) - 48), i++;
        
        A[++j] = x;
        
        x = 0, i++;
        
    }
    
    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;
}