Cod sursa(job #1838314)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 31 decembrie 2016 17:56:00
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>

using namespace std;
int n,x,y,z,i,j,l,st,dr,m,mini,k,a[100005],rmq1[20][100005],rmq2[20][100005];
int cost(int lu)
{
    l=a[lu];
    mini=max(rmq1[l][1], rmq1[l][lu-(1<<l)+1])-min(rmq2[l][1], rmq2[l][lu-(1<<l)+1]);
    for(i=2; i<=n-lu+1; i++)
    {
        k=max(rmq1[l][i], rmq1[l][i+lu-(1<<l)])-min(rmq2[l][i], rmq2[l][lu-(1<<l)+i]);
        if(k<mini) mini=k;
    }
    return mini;
}
int poz(int lu)
{
    int p;
    l=a[lu];
    mini=max(rmq1[l][1],rmq1[l][lu-(1<<l)+1])-min(rmq2[l][1], rmq2[l][lu-(1<<l)+1]);
    p=1;
    for(i=2; i<=n-lu+1; i++)
    {
        k=max(rmq1[l][i],rmq1[l][i+lu-(1<<l)])-min(rmq2[l][i], rmq2[l][lu-(1<<l)+i]);
        if(k<mini)
        {
            mini=k;
            p=i;
        }
        else if(k==mini/*&&rmq1[0][p]<=rmq1[0][i]*/) p=i;
    }
    return p;
}
int main()
{
    ifstream f("sir.in");
    ofstream g("sir.out");
    f>>n>>x>>y>>z;
    for(i=1; i<=n; i++)
    {
        f>>rmq1[0][i];
        rmq2[0][i]=rmq1[0][i];
    }
    for(i=2; i<100000; i*=2)
        a[i]=1;
    for(i=1; i<=100000; i++)
        a[i]+=a[i-1];
    for(i=1; 1<<i <=n; i++)
    {
        l=1<<(i-1);
        for(j=1; j<=n-2*l+1; j++)
        {
            rmq1[i][j]=max(rmq1[i-1][j],rmq1[i-1][j+l]);
            rmq2[i][j]=min(rmq2[i-1][j],rmq2[i-1][j+l]);
        }
    }
    if(cost(x)>z) g<<"-1\n";
    else if(cost(y)<z) g<<"-1\n";
    else
    {
        st=x;
        dr=y;
        while(st+1<dr)
        {
            m=(st+dr)/2;
            if(cost(m)<=z) st=m;
            else dr=m;
        }
        if(cost(dr)>z) dr=st;
        g<<dr<<" "<<poz(dr)<<" "<<poz(dr)+dr-1<<'\n';
    }
    f.close(); g.close();
    return 0;
}