Cod sursa(job #2676349)

Utilizator cyg_mihaizMIHAI ZARAFIU cyg_mihaiz Data 24 noiembrie 2020 09:01:09
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <deque>
#include <climits>

#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")

using namespace std;
const int NMAX=500000;

deque <int> Q;
int v[NMAX+5];

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    int n,k,i,minx,start,endx;
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin.close();
    minx=INT_MIN;
    for(i=1;i<=n;i++)
    {
        while(!Q.empty() and v[Q.back()]>v[i])
            Q.pop_back();
        Q.push_back(i);
        if(!Q.empty() and Q.front()<=i-k)
            Q.pop_front();
        if(v[Q.front()]>minx and i>=k){
            minx=v[Q.front()];
            start=i-k+1;
            endx=i;
        }
    }
    fout<<start<<" "<<endx<<" "<<minx;
    fout.close();
    return 0;
}