Cod sursa(job #1853115)

Utilizator edicCiuculescu Eduard edic Data 21 ianuarie 2017 14:03:13
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct inter{int st,dr;};
struct steve{int v,c;};
inter v[100001];
steve stiv[150001];
bool sor(inter a,inter b)
{
    return a.dr<b.dr;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,i,h=0,mid,poz;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&v[i].st,&v[i].dr);
    }
    for(i=1;i<=150000;i++)
    {
        stiv[i].c=1e9+1;
    }
    sort(v+1,v+n+1,sor);
    for(i=1;i<=n;i++)
    {
        mid=1<<16;
        poz=0;
        while(mid>0)
        {
            if(stiv[poz+mid].c<=v[i].st)
            {
                poz+=mid;
            }
            mid/=2;
        }
        if(stiv[poz].v+v[i].dr-v[i].st>stiv[h].v)
        {
            h++;
            stiv[h].v=stiv[poz].v+v[i].dr-v[i].st;
            stiv[h].c=v[i].dr;
        }
    }
    printf("%d",stiv[h].v);
    return 0;
}