Submission #643854

#TimeUsernameProblemLanguageResultExecution timeMemory
643854ymmDivide and conquer (IZhO14_divide)C++17
100 / 100
46 ms14940 KiB
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
struct obj { ll x, g, e, gm, em; } a[N], b[N];
int n;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n)
		cin >> a[i].x >> a[i].g >> a[i].e;
	Loop (i,1,n) {
		a[i].gm = a[i-1].g;
		a[i].em = a[i-1].e;
		a[i].g += a[i].gm;
		a[i].e += a[i].em;
	}
	Loop (i,0,n) {
		a[i].e -= a[i].x;
		a[i].em -= a[i].x;
	}
	memcpy(b, a, sizeof(b));
	sort(a, a+n, [](obj &x, obj &y){return x.e < y.e;});
	sort(b, b+n, [](obj &x, obj &y){return x.em < y.em;});
	ll ans = 0;
	ll mn = 1e18;
	for (int i=0, j=0; i < n; ++i) {
		while (j < n && b[j].em <= a[i].e) {
			mn = min(mn, b[j].gm);
			++j;
		}
		ans = max(ans, a[i].g - mn);
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...