Cod sursa(job #2639323)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 1 august 2020 13:53:18
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <cstring>

using namespace std;

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

const int DIM = 10005;

long long DP[DIM],n,Tree[DIM*4+5],sol;

struct Point
{
    int x,y,val;
}P[DIM];

void Read()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        {
            fin>>P[i].x>>P[i].y;
            P[i].val=P[i].y-P[i].x;
        }
}

bool Compare(Point a, Point b)
{
    return a.y<b.y;
}

void BuildTree(int nod, int st, int dr)
{
    if(st==dr)
        {
            Tree[nod]=DP[st];
            return;
        }
    int mij=(st+dr)/2;
    BuildTree(2*nod,st,mij);
    BuildTree(2*nod+1,mij+1,dr);
    Tree[nod]=max(Tree[2*nod],Tree[2*nod+1]);
}

void UpdateTree(int node, int st, int dr, int pos, long long val)
{
    if(st==dr)
    {
        Tree[node]+=val;
        return;
    }
    int mij=(st+dr)/2;
    if(pos<=mij)
        UpdateTree(2*node,st,mij,pos,val);
    else
        UpdateTree(2*node+1,mij+1,dr,pos,val);
    Tree[node]=max(Tree[2*node],Tree[2*node+1]);
}

void QueryTree(int node, int st, int dr, int a, int b)
{
    if(st>=a && dr<=b)
    {
        sol=max(sol,Tree[node]);
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        QueryTree(2*node,st,mij,a,b);
    if(b>mij)
        QueryTree(2*node+1,mij+1,dr,a,b);
}

int Search(int value)
{
    int st=1,dr=n,ans=0;
    while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(P[mij].y<=value)
                {
                    ans=max(ans,mij);
                    st=mij+1;
                }
            else
                dr=mij-1;
        }
    return ans;
}

void Solve()
{
    for(int i=1;i<=n;i++)
        DP[i]=P[i].val;
    BuildTree(1,1,n);
    for(int i=2;i<=n;i++)
        {
            int Find=P[i].x;
            int pos=Search(Find);
            sol=0;
            QueryTree(1,1,n,1,pos);
            DP[i]+=sol;
            UpdateTree(1,1,n,i,sol);
        }
}

void Print()
{
    long long ans=0;
    for(int i=1;i<=n;i++)
            ans=max(ans,DP[i]);
    fout<<ans<<'\n';
}

int main()
{
    Read();
    sort(P+1,P+1+n,Compare);
    Solve();
    Print();
}