Cod sursa(job #1937883)

Utilizator ZanoxNonea Victor Zanox Data 24 martie 2017 12:54:04
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define range 666013
#define lng long long

using namespace std;

fstream f("secventa.in",ios::in),g("secventa.out",ios::out);

int n,v[500001],ap[60001],o[60001],h[60002],hl,k,sol,sol1,sol2,i;

void swtch(int i,int j)
{
    int aux=h[i];
    h[i]=h[j];
    h[j]=aux;
    o[h[i]+30000]=i;
    o[h[j]+30000]=j;
}

void up(int i)
{
    if(i>1&&h[i/2]>h[i])
    {
        swtch(i,i/2);
        up(i/2);
    }
}

void add(int i)
{
    if(ap[i+30000]>0)
    {
        ap[i+30000]++;
    }
    else
    {
        ap[i+30000]++;
        h[++hl]=i;
        o[i+30000]=hl;
        up(hl);
    }
}

void roll(int i)
{
    if(i*2<hl)
    {
        if(h[i*2]<h[i*2+1])
        {
            swtch(i,i*2);
            roll(i*2);
        }
        else
        {
            swtch(i,i*2+1);
            roll(i*2+1);
        }
    }
    else if(i<hl)
    {
        swtch(i,hl);
        up(i);
    }
}

void del(int i)
{
    if(ap[i+30000]>1)
    {
        ap[i+30000]--;
    }
    else
    {
        roll(o[i+30000]);
        hl--;
        ap[i+30000]--;
    }
}

int main()
{
    f>>n>>k;
    sol=-30001;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
        add(v[i]);
        //for(int j=1;j<=hl;j++)cout<<h[j]<<' ';
        //cout<<'\n';
        if(i>k)del(v[i-k]);
        //for(int j=1;j<=hl;j++)cout<<h[j]<<' ';
        //cout<<'\n';
        //cout<<'\n';
        if(h[1]>sol&&i>=k)
        {
            sol1=i-k+1;
            sol2=i;
            sol=h[1];
        }
    }
    g<<sol1<<' '<<sol2<<' '<<sol;
}