Pagini recente » Cod sursa (job #2185305) | Cod sursa (job #613496) | Cod sursa (job #79118) | Cod sursa (job #1522904) | Cod sursa (job #2856065)
#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;
}