Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- //#define mp make_pair
- #define pb push_back
- using namespace std;
- typedef long long ll;
- const int MOD = 1e9 + 7;
- const int N = 1e5 + 9;
- const int INF = 1e9 + 5;
- struct treeNode {
- int sum, maxSubArray, maxPrefix, maxSuffix;
- treeNode () {
- sum = maxSubArray = maxPrefix = maxSuffix = 0;
- }
- treeNode (int sumT, int maxSubArrayT, int maxPrefixT, int maxSuffixT) {
- sum = sumT;
- maxSubArray = maxSubArrayT;
- maxPrefix = maxPrefixT;
- maxSuffix = maxSuffixT;
- }
- } segTree[4 * N];
- vector <pair <int, pair <int, int> > > intervals;
- vector <int> compressed, tmp;
- treeNode mergeNodes (treeNode leftNode, treeNode rightNode) {
- treeNode mergedNode (0, 0, 0, 0);
- mergedNode.sum = leftNode.sum + rightNode.sum;
- mergedNode.maxSubArray = max (max(leftNode.maxSubArray, rightNode.maxSubArray), leftNode.maxSuffix + rightNode.maxPrefix);
- mergedNode.maxPrefix = max (leftNode.maxPrefix, leftNode.sum + rightNode.maxPrefix);
- mergedNode.maxSuffix = max (rightNode.maxSuffix, rightNode.sum + leftNode.maxSuffix);
- return mergedNode;
- }
- void updateTree (int v, int l, int r, int idx, int val) {
- if (l == r) {
- int newVal = val + segTree[v].sum;
- segTree[v] = treeNode (newVal, newVal, newVal, newVal);
- return;
- }
- int mid = (l + r) / 2;
- if (idx <= mid)
- updateTree (2 * v, l, mid, idx, val);
- else updateTree (2 * v + 1, mid + 1, r, idx, val);
- segTree[v] = mergeNodes (segTree[2 * v], segTree[2 * v + 1]);
- }
- treeNode getQuery (int v, int l, int r, int L, int R) {
- if (L <= l && r <= R)
- return segTree[v];
- if (l > R || r < L)
- return treeNode (0, -1, -1, -1);
- int mid = (l + r) / 2;
- treeNode Q1 = getQuery (2 * v, l, mid, L, R);
- treeNode Q2 = getQuery (2 * v + 1, mid + 1, r, L, R);
- return mergeNodes (Q1, Q2);
- }
- int getIdx (int x) {
- return upper_bound (compressed.begin(), compressed.end(), x) - compressed.begin();
- }
- void solve () {
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++) {
- int l, r, val;
- cin >> l >> r >> val;
- intervals.push_back ({l, {r, val}});
- tmp.push_back (r);
- }
- sort (intervals.begin(), intervals.end());
- sort (tmp.begin(), tmp.end());
- for (int i = 0; i < (int) tmp.size(); i++) {
- if (i == 0) {
- compressed.pb (tmp[i]);
- continue;
- }
- if (tmp[i] != tmp[i - 1])
- compressed.pb (tmp[i]);
- }
- int res = 0;
- for (int i = 0; i < (int) intervals.size(); i++) {
- for (int j = i; j >= 0; j--) {
- updateTree (1, 1, n, getIdx(intervals[j].S.F), intervals[j].S.S);
- treeNode ans = getQuery (1, 1, n, 1, n);
- res = max (res, ans.maxSubArray);
- }
- for (int i = 0; i < 4 * N; i++)
- segTree[i] = treeNode (0, 0, 0, 0);
- }
- cout << res << "\n";
- return;
- }
- int main () {
- int t = 1;
- //cin >> t;
- while (t--)
- solve ();
- return 0;
- }
Add Comment
Please, Sign In to add comment