Cod sursa(job #1808333)

Utilizator martonsSoos Marton martons Data 17 noiembrie 2016 16:59:35
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 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]){
                break;
            }
            else 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;
}