Cod sursa(job #2866183)

Utilizator biancalautaruBianca Lautaru biancalautaru Data 9 martie 2022 13:44:00
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,i,st,dr,mid,maxi,d[100001];
struct interval {
    int x,y;
}v[100001];

bool cmp(interval a,interval b) {
    return a.y<=b.y;
}

int main() {
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    d[0]=0;
    for (i=1;i<=n;i++) {
        d[i]=max(d[i-1],v[i].y-v[i].x);
        st=1;
        dr=i-1;
        while (st<=dr) {
            mid=(st+dr)/2;
            if (v[i].x>=v[mid].y)
                st=mid+1;
            else
                dr=mid-1;
        }
        d[i]=max(d[i],d[dr]+v[i].y-v[i].x);
        if (d[i]>maxi)
            maxi=d[i];
    }
    fout<<maxi;
    return 0;
}