Advertisement
GerONSo

Untitled

Jun 20th, 2018
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.63 KB | None | 0 0
  1. /*
  2. --┬-- | | --┬-- | |
  3. | |\ | | | |
  4. | | \ | | -----> | |
  5. | | \ | | | |
  6. | | \ | | | |
  7. --┴-- | \| | └---- └----
  8.  
  9. */
  10.  
  11. #define pragma
  12.  
  13. #ifdef pragma
  14. #pragma GCC optimize("Ofast")
  15. #pragma GCC optimize("no-stack-protector")
  16. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  17. #pragma GCC optimize("unroll-loops")
  18. #endif // pragma
  19.  
  20. #include<bits/stdc++.h>
  21. #include<string>
  22.  
  23. #define ll long long
  24. #define all(x) begin(x),end(x)
  25. #define pb push_back
  26. #define x first
  27. #define y second
  28. #define INF 9223372036854775807ll
  29. #define PI 3.14159265359d
  30. #define INPUT "input.txt"
  31. #define OUTPUT "output.txt"
  32. #define sz size
  33. #define rsz resize
  34. #define int long long
  35.  
  36. using namespace std;
  37.  
  38. typedef vector<int> vi;
  39. typedef vector<bool> vb;
  40. typedef pair<int,int> pii;
  41. typedef long double ld;
  42. typedef vector<vi> matrix;
  43.  
  44. void seriy() {
  45. ios::sync_with_stdio(0);
  46. cin.tie(0);
  47. cout.tie(0);
  48. #ifdef _android
  49. freopen("input", "r", stdin);
  50. freopen("output", "w", stdout);
  51. #else
  52. //_android
  53. #endif
  54. }
  55.  
  56. struct node {
  57. int val, df;
  58. };
  59.  
  60. node t[10000000 * 8];
  61.  
  62. void push(int v) {
  63. t[v].val += t[v].df;
  64. t[v * 2 + 1].df += t[v].df;
  65. t[v * 2 + 2].df += t[v].df;
  66. t[v].df = 0;
  67. }
  68.  
  69. void update(int v, int l, int r, int tl, int tr, int val) {
  70. //cerr << tl << " " << tr << " " << l << " " << r << endl;
  71. push(v);
  72. if(tl > r || tr < l) {
  73. return;
  74. }
  75. if(tl >= l && tr <= r) {
  76. t[v].df += val;
  77. push(v);
  78. return;
  79. }
  80. int tm = (tl + tr) >> 1;
  81. update(v * 2 + 1, l, r, tl, tm, val);
  82. update(v * 2 + 2, l, r, tm + 1, tr, val);
  83. t[v].val = max(t[v * 2 + 1].val, t[v * 2 + 2].val);
  84. }
  85.  
  86. int getmax(int v, int l, int r, int tl, int tr) {
  87. push(v);
  88. if(tl > r || tr < l) {
  89. return -1;
  90. }
  91. if(tl >= l && tr <= r) {
  92. return t[v].val;
  93. }
  94. int tm = (tl + tr) >> 1;
  95. int x = getmax(v * 2 + 1, l, r, tl, tm);
  96. int y = getmax(v * 2 + 2, l, r, tm + 1, tr);
  97. return max(x, y);
  98. }
  99.  
  100. signed main(){
  101. seriy();
  102. int n, m;
  103. cin >> n >> m;
  104. for(int i = 0; i < m; i++) {
  105. int l, r, val;
  106. cin >> l >> r >> val;
  107. l--, r--;
  108. update(0, l, r, 0, n - 1, val);
  109. }
  110. cout << getmax(0, 0, n - 1, 0, n - 1);
  111. // cout << endl;
  112. // for(auto i : t) cout << i.val << " ";
  113. return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement