Cod sursa(job #2808385)

Utilizator SeracovanuEdwardSeracovanu Edward SeracovanuEdward Data 24 noiembrie 2021 23:01:29
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;
class parsare{
private:
    FILE *fin;
    char *buff;
    int sp;
    char read_ch(){
    ++sp;
    if(sp==4096){
        sp=0;
        fread(buff,1,4096,fin);
    }
    return buff[sp];
    }
public:
    parsare(const char *name){
    fin=fopen(name,"r");
    buff=new char [4096]();
    sp=4095;
    }
    parsare& operator >> (int &n){
    char c;
    int sgn=1;
    while(!isdigit(c=read_ch()) && c!='-');
    if(c=='-'){
        sgn=-1;
        n=0;
    }else n=c-'0';
    while(isdigit(c=read_ch()))
        n=n*10+c-'0';
    n=n*sgn;
    return *this;
    }
};
int n,k;
const int nmax=1e5;
int arr[5*nmax+5];
int bazamaxima,finalpos;
deque <int> q;
FILE *g=fopen("secventa.out","w");
int main()
{
    parsare fin("secventa.in");
    fin>>n>>k;
    for(int i=0;i<n;++i)
        fin>>arr[i];
    int i;
    for(i=0;i<k;++i){
        while(!q.empty() && arr[i]<=arr[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    for(;i<n;++i){
        if(arr[q.front()]>bazamaxima){
            bazamaxima=arr[q.front()];
            finalpos=i-k+1;
        }
        while(!q.empty() && q.front()<=i-k)
            q.pop_front();
        while(!q.empty() && arr[i]<=arr[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    if(arr[q.front()]>bazamaxima){
        bazamaxima=arr[q.front()];
        finalpos=n-k+1;
    }
    fprintf(g,"%d %d %d",finalpos,finalpos+k-1,bazamaxima);
}