Cod sursa(job #2268213)

Utilizator SweetHumanAvram Gheorghe SweetHuman Data 24 octombrie 2018 16:34:40
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream f1("secventa.in");
ofstream f2("secventa.out");

int n,k;
char s[3500005];
int poz=0;
int v[500005];
deque<int> pozitii;
int maxim, finalSecvMaxim;

int next(){
    while((s[poz] <'0' || s[poz]>'9') && s[poz]!='-'){
        poz++;
    }
    int nr = 1;
    if(s[poz]=='-') {
        nr=-1*(s[poz+1]-'0');
        poz+=2;
    }
    else{
        nr=s[poz]-'0';
        poz++;
    }
    while(s[poz] >='0' && s[poz]<='9'){
        nr=nr*10+(s[poz]-'0');
        poz++;
    }
    return nr;
}

int main() {
    f1>>n>>k;
    finalSecvMaxim=k-1;
    f1.get();
    f1.getline(s,3500005);
    for(int i=0;i<n;i++){
        v[i]=next();
    }
    pozitii.push_back(0);
    for(int i=1;i<k;i++){
        while(v[pozitii.back()]>v[i]){
            pozitii.pop_back();
        }
        pozitii.push_back(i);
    }
    maxim=pozitii.front();
    finalSecvMaxim=k-1;
    for(int i=k;i<n;i++){
        if(pozitii.front()<=i-k) pozitii.pop_front();
        while(!pozitii.empty() && v[pozitii.back()]>v[i]){
            pozitii.pop_back();
        }
        pozitii.push_back(i);
        if(v[maxim]<v[pozitii.front()]){
            maxim=pozitii.front();
            finalSecvMaxim=i;
        }
    }
    f2<<finalSecvMaxim-(k-2)<<" "<<finalSecvMaxim+1<<" "<<v[maxim];
    return 0;
}