Submission #1366055

#TimeUsernameProblemLanguageResultExecution timeMemory
1366055blackscreen1Divide and conquer (IZhO14_divide)C++20
100 / 100
40 ms8840 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, a[100005], b[100005], c[100005], cans = 0;
set<pll> st;
pll p;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	iloop(0, n) cin >> a[i] >> b[i] >> c[i];
	iloop(1, n) b[i] += b[i-1], c[i] += c[i-1];
	iloop(0, n) {
		p = {(i ? c[i-1] : 0) - a[i], (i ? b[i-1] : 0)};
		auto it = st.upper_bound({p.first, INF});
		if (it != st.begin()) {
			it--;
			if ((*it).second > p.second) {
				if ((*it).first < p.first) it++;
				while (it != st.end() && (*it).second >= p.second) {
					auto it2 = it;
					it++;
					st.erase(it2);
				}
				st.insert(p);
			}
		}
		else {
			while (it != st.end() && (*it).second >= p.second) {
				auto it2 = it;
				it++;
				st.erase(it2);
			}
			st.insert(p);
		}
		it = st.upper_bound({c[i] - a[i], INF});
		if (it != st.begin()) {
			it--;
			cans = max(cans, b[i] - (*it).second);
		}
		/*cout << i << ":";
		for (auto it : st) cout << it.first << " " << it.second << ",";
		cout << endl;*/
	}
	cout << cans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...