Cod sursa(job #2740453)

Utilizator cegaxEmanuel Soto Ortega cegax Data 13 aprilie 2021 00:36:50
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define pb push_back 
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

bool mycmp(const ii& a, const ii& b) {
	return a.first < b.first || (a.first == b.first and a.second < b.second);
}

struct cmp {
	bool operator() (const ii& a, const ii &b) const {
		return a.first < b.first;
	}
};

int main() {
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin >> n;
	vii a(n);

	for(int i = 0; i < n; i++)
		cin >> a[i].first >> a[i].second;
	
	sort(all(a), mycmp);

	int ans = 0;
	int prev = 0;

	set<ii, cmp> toAdd;

	for(int i = 0; i < n; i++) {
		while(!toAdd.empty()) {
			ii v = *toAdd.begin();
			if(v.first <= a[i].first) {
				prev = max(prev, v.second);
				toAdd.erase(v);
			}
			else break;
		}
		int val = prev+a[i].second-a[i].first;
		ans = max(ans, val);
		toAdd.insert({a[i].second, val});
	}

	cout << ans << "\n";
	
	return 0;
}