Cod sursa(job #2912742)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 10 iulie 2022 14:35:47
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");

int n,x,l,l2,suma;

int r[17][100005];
int e[100005];

struct numar{
 int d;
 int val;
}v[100005];

void process()
{
    r[0][1]=v[1].val;
    for(int i=2;i<=n;i++)
    {
        r[0][i]=v[i].val;
        e[i] = 1+e[i/2];
    }

    for(int p=1;(1<<p)<=n;p++)
    {
        for(int i=1;i<=n;i++)
        {
            r[p][i]=r[p-1][i];
            int j = i + (1<<(p-1));
            if(j<=n && r[p][i]<r[p-1][j])
                r[p][i]=r[p-1][j];
        }
    }
}


int cmp(numar a,numar b)
{
    if(a.d != b.d)
        return a.d<b.d;
    return a.val<b.val;
}

int b_search_d()
{
    int st=1;int dr=n;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(v[mid].d+l2>x)
        {
            dr=mid-1;

        }
        else{

            st=mid+1;
        }
    }
    return st;
}

int main()
{
    fin>>n>>x>>l;
    l2=l;

    for(int i=1;i<=n;i++)
        fin>>v[i].d>>v[i].val;
    sort(v+1,v+n+1,cmp);
    process();
    int poz = -1;
    while(1)
    {
        int maxim = -1;
        poz = b_search_d();

        for(int i=poz;i<=n;i++)
        {
            maxim=max(maxim,v[i].val);
        }


        int E = e[n-poz+1];
        int len = (1<<E);
        suma+=max(r[E][poz],r[E][n+1-len]);
        n=poz-1;
        l2+=l;
        if(v[1].d+l2-l>x)
            break;


    }
    fout<<suma;


}

/*
0 7
1 13
3 16
3 16
4 3
4 10
4 14
4 18
5 16
6 7

16 18 13 7
*/