Fshl0

kharaaa

Jan 16th, 2022 (edited)
216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. //#define mp make_pair
  5. #define pb push_back
  6.  
  7. using namespace std;
  8. typedef long long ll;
  9.  
  10. const int MOD = 1e9 + 7;
  11. const int N = 1e5 + 9;
  12. const int INF = 1e9 + 5;
  13.  
  14. struct treeNode {
  15.     int sum, maxSubArray, maxPrefix, maxSuffix;
  16.    
  17.     treeNode () {
  18.         sum = maxSubArray = maxPrefix = maxSuffix = 0;
  19.     }
  20.    
  21.     treeNode (int sumT, int maxSubArrayT, int maxPrefixT, int maxSuffixT) {
  22.         sum = sumT;
  23.         maxSubArray = maxSubArrayT;
  24.         maxPrefix = maxPrefixT;
  25.         maxSuffix = maxSuffixT;
  26.     }
  27. } segTree[4 * N];
  28.  
  29. vector <pair <int, pair <int, int> > > intervals;
  30. vector <int> compressed, tmp;
  31.  
  32. treeNode mergeNodes (treeNode leftNode, treeNode rightNode) {
  33.     treeNode mergedNode (0, 0, 0, 0);
  34.    
  35.     mergedNode.sum = leftNode.sum + rightNode.sum;
  36.     mergedNode.maxSubArray = max (max(leftNode.maxSubArray, rightNode.maxSubArray), leftNode.maxSuffix + rightNode.maxPrefix);
  37.     mergedNode.maxPrefix = max (leftNode.maxPrefix, leftNode.sum + rightNode.maxPrefix);
  38.     mergedNode.maxSuffix = max (rightNode.maxSuffix, rightNode.sum + leftNode.maxSuffix);
  39.    
  40.     return mergedNode;
  41. }
  42.  
  43. void updateTree (int v, int l, int r, int idx, int val) {
  44.     if (l == r) {
  45.         int newVal = val + segTree[v].sum;
  46.         segTree[v] = treeNode (newVal, newVal, newVal, newVal);
  47.        
  48.         return;
  49.     }
  50.    
  51.     int mid = (l + r) / 2;
  52.     if (idx <= mid)
  53.         updateTree (2 * v, l, mid, idx, val);
  54.     else updateTree (2 * v + 1, mid + 1, r, idx, val);
  55.    
  56.     segTree[v] = mergeNodes (segTree[2 * v], segTree[2 * v + 1]);
  57. }
  58.  
  59. treeNode getQuery (int v, int l, int r, int L, int R) {
  60.     if (L <= l && r <= R)
  61.         return segTree[v];
  62.    
  63.     if (l > R || r < L)
  64.         return treeNode (0, -1, -1, -1);
  65.    
  66.     int mid = (l + r) / 2;
  67.     treeNode Q1 = getQuery (2 * v, l, mid, L, R);
  68.     treeNode Q2 = getQuery (2 * v + 1, mid + 1, r, L, R);
  69.    
  70.     return mergeNodes (Q1, Q2);
  71. }
  72.  
  73. int getIdx (int x) {
  74.     return upper_bound (compressed.begin(), compressed.end(), x) - compressed.begin();
  75. }
  76.  
  77. void solve () {
  78.     int n;
  79.     cin >> n;
  80.    
  81.     for (int i = 1; i <= n; i++) {
  82.         int l, r, val;
  83.         cin >> l >> r >> val;
  84.        
  85.         intervals.push_back ({l, {r, val}});
  86.         tmp.push_back (r);
  87.     }
  88.    
  89.     sort (intervals.begin(), intervals.end());
  90.     sort (tmp.begin(), tmp.end());
  91.    
  92.     for (int i = 0; i < (int) tmp.size(); i++) {
  93.         if (i == 0) {
  94.             compressed.pb (tmp[i]);
  95.            
  96.             continue;
  97.         }
  98.        
  99.         if (tmp[i] != tmp[i - 1])
  100.             compressed.pb (tmp[i]);
  101.     }
  102.    
  103.     int res = 0;
  104.     for (int i = 0; i < (int) intervals.size(); i++) {
  105.         for (int j = i; j >= 0; j--) {
  106.             updateTree (1, 1, n, getIdx(intervals[j].S.F), intervals[j].S.S);
  107.            
  108.             treeNode ans = getQuery (1, 1, n, 1, n);
  109.             res = max (res, ans.maxSubArray);
  110.         }
  111.        
  112.         for (int i = 0; i < 4 * N; i++)
  113.             segTree[i] = treeNode (0, 0, 0, 0);
  114.     }
  115.    
  116.     cout << res << "\n";
  117.     return;
  118. }
  119.  
  120. int main () {
  121.     int t = 1;
  122.     //cin >> t;
  123.    
  124.     while (t--)
  125.         solve ();
  126.    
  127.     return 0;
  128. }
  129.  
  130.  
  131.  
Add Comment
Please, Sign In to add comment