Pagini recente » Cod sursa (job #1220138) | Istoria paginii runda/oni_4 | Cod sursa (job #1155643) | Cod sursa (job #1923745) | Cod sursa (job #1898529)
#include <bits/stdc++.h>
#define y second
#define x first
typedef long long ll;
using namespace std;
ll N,D[100100],I[100100],rs;
pair<ll,ll> A[100100];
int caut(ll y){
int st=1,dr=N;
while(st<dr-3){
int mid = (st+dr)/2;
if(y<=A[mid].x) dr = mid;
else st = mid;
}
for(;st<=dr;st++) if(A[st].x>=y) return st;
return -1;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
cin >> N;
for(ll i = 1,x,y;i<=N;i++){
cin >> x >> y;
A[i] = make_pair(x,y);
}
sort(A+1,A+1+N);
// for(int i = 1;i<=N;i++) cout << A[i].x << ' ' << A[i].y << '\n';
for(int i = 1;i<=N;i++){
if(D[I[i-1]] > D[I[i]]) I[i] = I[i-1];
D[i] = A[i].y - A[i].x + D[I[i]];
rs=max(rs,D[i]);
int up = caut(A[i].y);
if(up > 0 && D[I[up]] < D[i]) I[up]=i;
// for(int j = 1;j<=N;j++) cout << I[j] << "\n "[j<N];
// for(int j = 1;j<=N;j++) cout << D[j] << "\n "[j<N];
}
cout << rs;
}