Cod sursa(job #1851113)

Utilizator tudi98Cozma Tudor tudi98 Data 19 ianuarie 2017 12:40:31
Problema Heavy metal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;

const int Nmax = 100000;

int n;

struct segment
{
    int a,b;
    segment(): a(0),b(0) {}
};

unordered_map<int,int> H;
vector<segment> segm;
set<int> s;
int aint[Nmax*4+5];

void update(int p,int val)
{
    p += n;
    aint[p] = max(val,aint[p]);
    for (; p > 1; p >>= 1)
        aint[p>>1] = max(aint[p],aint[p^1]);
}

int query(int l,int r)
{
    int ret = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
    {
        if (l&1)
        {
            ret = max(ret,aint[l]);
            l++;
        }
        if (r & 1)
        {
            r--;
            ret = max(ret,aint[r]);
        }
    }
    return ret;
}

bool comp(const segment &A,const segment &B)
{
    if (A.a == B.a)
        return A.b < B.b;
    return A.a < B.a;
}

int main()
{
    ifstream fin("heavymetal.in");
    ofstream fout("heavymetal.out");

    fin >> n;
    segm = vector<segment>(n+1);
    for (int i = 1; i <= n; i++)
    {
        fin >> segm[i].a >> segm[i].b;
        s.insert(segm[i].a);
        s.insert(segm[i].b);
    }

    int m = 0;
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
        H[*it] = ++m;

    sort(segm.begin()+1,segm.end(),comp);

    int best = 0;
    for (int i = 1; i <= n; i++)
    {
        int R = H[segm[i].a];
        int ans = query(0,R-1);
        ans += segm[i].b - segm[i].a;
        update(H[segm[i].b]-1,ans);
        best = max(best,ans);
    }

    fout << best;
}