fork download 
  1. #include <algorithm>
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. const int MAXN = 1e5;
  6. const int INF = 2e9;
  7.  
  8. struct Node
  9. {
  10.     long long best_l, best_r, best, sum;
  11.     int lazy;
  12.  
  13.     Node(long long bl = 0, long long br = 0, long long b = 0, long long s = 0, int lz = INF)
  14.         : best_l(bl), best_r(br), best(b), sum(s), lazy(lz) {}
  15. };
  16.  
  17. int n, q;
  18. Node node[MAXN * 4 + 5];
  19.  
  20. Node combine(const Node &left, const Node &right)
  21. {
  22.     Node dest;
  23.     dest.sum = left.sum + right.sum;
  24.     dest.best_l = max(left.best_l, left.sum + right.best_l);
  25.     dest.best_r = max(right.best_r, right.sum + left.best_r);
  26.     dest.best = max({left.best, right.best, left.best_r + right.best_l});
  27.     return dest;
  28. }
  29.  
  30. void down(int id, int l, int r)
  31. {
  32.     long long lz = node[id].lazy;
  33.     node[id].lazy = INF;
  34.     if (lz == INF) {
  35.         return;
  36.     }
  37.     long long val = max(0LL, lz * (r - l + 1));
  38.     node[id] = {val, val, val, lz * (r - l + 1), INF};
  39.     if (l < r) {
  40.         node[id * 2].lazy = lz;
  41.         node[id * 2 + 1].lazy = lz;
  42.     }
  43. }
  44.  
  45. Node query(int u, int v, int id = 1, int l = 1, int r = n)
  46. {
  47.     down(id, l, r);
  48.     if (u > r || v < l) {
  49.         return Node();
  50.     }
  51.     if (u <= l && r <= v) {
  52.         return node[id];
  53.     }
  54.     int mid = (l + r) / 2;
  55.     Node left = query(u, v, id * 2, l, mid);
  56.     Node right = query(u, v, id * 2 + 1, mid + 1, r);
  57.     return combine(left, right);
  58. }
  59.  
  60. void update(int u, int v, int x, int id = 1, int l = 1, int r = n)
  61. {
  62.     down(id, l, r);
  63.     if (u > r || v < l) {
  64.         return;
  65.     }
  66.     if (u <= l && r <= v) {
  67.         node[id].lazy = x;
  68.         down(id, l, r);
  69.         return;
  70.     }
  71.     int mid = (l + r) / 2;
  72.     update(u, v, x, id * 2, l, mid);
  73.     update(u, v, x, id * 2 + 1, mid + 1, r);
  74.     node[id] = combine(node[id * 2], node[id * 2 + 1]);
  75. }
  76.  
  77. void solve()
  78. {
  79.     cin >> n >> q;
  80.     for (int i = 0; i < q; i++) {
  81.         int type, u, v, x;
  82.         cin >> type >> u >> v;
  83.         if (type == 1) {
  84.             cin >> x;
  85.             update(u, v, x);
  86.         }
  87.         else {
  88.             Node res = query(u, v);
  89.             cout << res.best << '\n';
  90.         }
  91.     }
  92. }
  93.  
  94. int main()
  95. {
  96.     ios::sync_with_stdio(false);
  97.     cin.tie(nullptr);
  98.  
  99.     solve();
  100.  
  101.     return 0;
  102. }
Success #stdin #stdout 0.01s 19296KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/O4Lzta
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!