Cod sursa(job #1806963)

Utilizator martonsSoos Marton martons Data 15 noiembrie 2016 21:05:15
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>

using namespace std;

int v[500000], d[500000], f=1, e=0, crte=1, crtf=1, n, k;
int best=-300000, bf, be;
int main()
{

    ifstream in("secventa.in");
    in>>n>>k;

    for(int i=0;i<n;i++){
        in>>v[i];

        //while(f <= e && v[d[e]]>v[i]) e--;
        int st = f;
        int en = e;
        int mid=e;
        while(st<=en){
            mid = (st+en)/2;
            if(v[d[mid]]<v[i]){
                st = mid+1;
            }
            else{
                en = mid-1;
            }
        }
        e = mid;

        d[++e] = i;
        if(i-d[f]+1>k)f++;

        if(i>=k-1){
            if(v[d[f]]>best){
                best = v[d[f]];
                bf = i-k+2;
                be = i+1;
            }
        }
    }

    ofstream out("secventa.out");
    out<<bf<<" "<<be<<" "<<best;
    return 0;
}