Cod sursa(job #1775888)

Utilizator grimmerFlorescu Luca grimmer Data 10 octombrie 2016 19:44:01
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <deque>
using namespace std;

int v[500001];
deque<int> q;
int max_base = -99999;
char buffer[4000000], *c = buffer;
ifstream cin("secventa.in");
ofstream cout("secventa.out");

int main()
{
    int i, k, n, l, r, x;
    cin>>n>>k>>ws;
    cin.getline(buffer, 4000000);

    for(i = 1; i <= n; ++i){
        bool neg = false;
        x = 0;

        while(*c == ' '){
            ++c;
        }
        if(*c == '-'){
            neg = true;
            ++c;
        }
        while(isdigit(*c)){
            x = x*10 + *c - '0';
            ++c;
        }
        if(neg){
            x *= -1;
        }

        v[i] = x;
        while(!q.empty() && v[q.back()] >= v[i]){
            q.pop_back();
        }

        q.push_back(i);

        while(!q.empty() && q.front() <= i-k){
            q.pop_front();
        }

        if(i >= k){
            if(v[q.front()] > max_base){
                max_base = v[q.front()];
                l = i - k + 1;
                r = i;
            }
        }
    }

    cout<<l<<" "<<r<<" "<<max_base;

    return 0;
}