Cod sursa(job #2384874)

Utilizator bluestorm57Vasile T bluestorm57 Data 21 martie 2019 11:41:04
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

int n,k;
int v[500001];
int deq[500001],poz, maxx, pozmin, minn;
const int inf = (1<<30);

int main(){
    int i,j;
    int n,k;
    f>>n>>k;
    for(i=1; i<=n; i++)
        f>>v[i];

    int m=n-k+1;

    deq[1]=inf;
    pozmin=0;

    for(j=1; j<=k; j++)
        if(v[j]<deq[1]){
            pozmin=j;
            deq[1]=v[j];
        }
        //deq[1]=min(deq[1], v[j]);

    for(i=2; i<=m; i++){

        if(pozmin>=i){
            if(v[i+k-1]<deq[i-1]){
                pozmin=i+k-1;
                deq[i]=v[i+k-1];
            }
        }
        else{
            deq[i]=inf;
            for(j=0; j<k; j++)
                if(deq[i]>v[i+j]){
                    deq[i]=v[i+j];
                    pozmin=i+j;
                }
        }

        // deq[i]=min(deq[i-1], v[i+k-1]);

        //for(j=0; j<k; j++)
         //   deq[i]=min(deq[i], v[i+j]);

        if(deq[i]>maxx){
            maxx=deq[i];
            poz=i;
        }
    }

     g<<poz<<" "<<poz+k-1<<" "<<maxx<<"\n";
     //for(i=1; i<=m; i++)
        //g<<deq[i]<<" ";

return 0;
}