Cod sursa(job #1984291)

Utilizator amaliarebAmalia Rebegea amaliareb Data 24 mai 2017 14:00:11
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define maxn 100000

using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct miau{long long st,dr;} v[maxn+5];
long long n,i,j,d[maxn+5],poz,maxi;

bool cmp(miau a, miau b)
{
    return a.dr<b.dr;
}

int cautbin(int val,int i)
{
    int ans=0,pas=1<<20;
    while(pas)
    {
        if(ans+pas<i && v[ans+pas].dr<val) ans+=pas;
        pas/=2;
    }
    return ans;
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++) f>>v[i].st>>v[i].dr;
    sort(v+1,v+n+1,cmp);
    d[1]=v[1].dr-v[1].st+1;
    for(i=2;i<=n;i++)
    {
        poz=cautbin(v[i].st,i);
        d[i]=v[i].dr-v[i].st+1+d[poz];
        d[i]=max(d[i],d[i-1]);
    }
    maxi=0;
    for(i=1;i<=n;i++) if(d[i]>maxi) maxi=d[i];
    g<<maxi<<'\n';
    return 0;
}