fork(8) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <utility>
  5. #include <algorithm>
  6. #include <stack>
  7. #include <queue>
  8. #include <deque>
  9. #include <map>
  10. #include <set>
  11.  
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <ctype.h>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long longs;
  19.  
  20. int ST[4001], Add[4001];
  21.  
  22. void Update(int k, int L, int R, int i, int j, int v)
  23. {
  24.     if (L > j || R < i) return;
  25.     if (i <= L && R <= j)
  26.     {
  27.         ST[k] += v;
  28.         Add[k] += v;
  29.         return;
  30.     }
  31.  
  32.     Add[k << 1] += Add[k];
  33.     Add[(k << 1) + 1] += Add[k];
  34.     ST[k << 1] += Add[k];
  35.     ST[(k << 1) + 1] += Add[k];
  36.     Add[k] = 0;
  37.  
  38.     int mid = (L + R) >> 1;
  39.     Update(k << 1, L, mid, i, j, v);
  40.     Update((k << 1) + 1, mid + 1, R, i, j, v);
  41.  
  42.     ST[k] = max(ST[k << 1], ST[(k << 1) + 1]);
  43. }
  44.  
  45. int Get(int k, int L, int R, int i, int j)
  46. {
  47.     if (L > j || R < i) return -1000000000;
  48.     if (i <= L && R <= j) return ST[k];
  49.  
  50.     Add[k << 1] += Add[k];
  51.     Add[(k << 1) + 1] += Add[k];
  52.     ST[k << 1] += Add[k];
  53.     ST[(k << 1) + 1] += Add[k];
  54.     Add[k] = 0;
  55.  
  56.     int mid = (L + R) >> 1;
  57.     return max(Get(k << 1, L, mid, i, j), Get((k << 1) + 1, mid + 1, R, i, j));
  58. }
  59.  
  60. int main()
  61. {
  62.     int N, M, k, x, y, v;
  63.  
  64.     cin >> N >> M;
  65.     while (M--)
  66.     {
  67.         cin >> k >> x >> y;
  68.         if (k) cout << Get(1, 1, N, x, y) << endl; else
  69.         {
  70.             cin >> v;
  71.             Update(1, 1, N, x, y, v);
  72.         }
  73.     }
  74.  
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 2760KB
comments (?)
stdin
copy 
3 5
0 1 2 3
0 2 3 5
1 1 3
1 2 3
1 1 2
stdout
copy 
8
8
8
https://ideone.com/ddfhfx
language:
C++ 4.3.2 (gcc-4.3.2)
created:
11 years ago
visibility:
secret

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!