Cod sursa(job #2856065)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 23 februarie 2022 12:26:50
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O2")
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int dp[100005],n,cnt=1,i,ans,last;
pair<int,int> a[200005],vl[100005];
bool cmp(pair<int,int> a, pair<int,int> b)
{
    if(a.second!=b.second)
        return a.second<b.second;
    return a.first<b.first;
}
map<int,bool> ok;
unordered_map<int,int> inv;
int aib[200005];
int ub(int i){return i&(-i);}
void update(int i, int v)
{
    for(;i<=cnt;i+=ub(i))
        aib[i]+=v;
}
int query(int i)
{
    int r=0;
    for(;i>0;i-=ub(i))
        r+=aib[i];
    return r;
}
signed main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i].first>>a[i].second;
        a[i].first++;
        a[i].second++;
        ok[a[i].first]=1;
        ok[a[i].second]=1;
    }
    for(auto it:ok)
        inv[it.first]=++cnt;
    for(i=1;i<=n;i++)
    {
        vl[i]=a[i];
        a[i].first=inv[a[i].first];
        a[i].second=inv[a[i].second];
    }
    sort(a+1,a+n+1,cmp);
    sort(vl+1,vl+n+1,cmp);
    dp[1]=vl[1].second-vl[1].first;
    int max1=dp[1];
    for(i=2;i<=n;i++)
    {
        dp[i]=vl[i].second-vl[i].first;
        dp[i]+=query(a[i].first);
        max1=max(max1,dp[i]);
        update(a[i].second,dp[i]);
    }
    /*for(i=1;i<=n;i++)
    {
        cout<<a[i].first<<' '<<a[i].second<<' '<<vl[i].first<<' '<<vl[i].second<<'\n';
    }
    for(i=1;i<=n;i++)
        cout<<dp[i]<<' ';*/
    fout<<max1<<'\n';
    return 0;
}