Advertisement
Hippskill

Untitled

Jan 18th, 2016
165
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <memory.h>
  7. #include <map>
  8. #include <set>
  9. #include <queue>
  10. #include <list>
  11. #include <sstream>
  12. #include <cstring>
  13. #include <cassert>
  14. #include <climits>
  15. #include <time.h>
  16. #include <stack>
  17. using namespace std;
  18.  
  19. const int N = 1e6 + 1;
  20. const int SIZE = (1 << 17);
  21. const int INF = 1e9;
  22.  
  23.  
  24. int add(int a, int b) {
  25.     return a + b;
  26. }
  27.  
  28. int mul(int a, int b) {
  29.     return a * b;
  30. }
  31.  
  32. struct segment_tree {
  33.     int t[2 * SIZE];
  34.     int pushing[2 * SIZE];
  35.  
  36.     segment_tree() : t(), pushing() {}
  37.  
  38.     void build(int n) {
  39.         for (int i = 0; i < n; i++)
  40.             t[SIZE + i] = 0;
  41.         for (int i = SIZE - 1; i > 0; i--) {
  42.             update(i);
  43.         }
  44.     }
  45.  
  46.     void apply(int v, int l, int r, int val) {
  47.         t[v] = ::add(t[v], mul(val, r - l + 1));
  48.         pushing[v] = ::add(pushing[v], val);
  49.     }
  50.  
  51.     void push(int v, int l, int r) {
  52.         int m = (r + l) / 2;
  53.         apply(2 * v, l, m, pushing[v]);
  54.         apply(2 * v + 1, m + 1, r, pushing[v]);
  55.         pushing[v] = 0;
  56.     }
  57.  
  58.     void update(int v) {
  59.         t[v] = ::add(t[2 * v], t[2 * v + 1]);
  60.     }
  61.    
  62.     void add(int v, int l, int r, int a, int b, int val) {
  63.         if (a > r || b < l)
  64.             return;
  65.         if (a <= l && r <= b) {
  66.             apply(v, l, r, val);
  67.             return;
  68.         }
  69.         int m = (r + l) / 2;
  70.         push(v, l, r);
  71.         add(2 * v, l, m, a, b, val);
  72.         add(2 * v + 1, m + 1, r, a, b, val);
  73.         update(v);
  74.     }
  75.  
  76.     void add(int a, int b, int val) {
  77.         add(1, 0, SIZE - 1, a, b, val);
  78.     }
  79.    
  80.     int get_value(int v, int l, int r, int p) {
  81.         if (l == r)
  82.             return t[v];
  83.         int m = (r + l) / 2;
  84.         push(v, l, r);
  85.         if (p <= m)
  86.             return get_value(2 * v, l, m, p);
  87.         return get_value(2 * v + 1, m + 1, r, p);
  88.     }
  89.    
  90.     int get_value(int p) {
  91.         return get_value(1, 0, SIZE - 1, p);
  92.     }
  93.  
  94.  
  95. } tree;
  96.  
  97. int main() {
  98.     //freopen("input.txt", "r", stdin);
  99.     //freopen("output.txt", "w", stdout);
  100.     int n;
  101.     scanf("%d", &n);
  102.     tree.build(n + 1);
  103.     for (int i = 0; i <= n; i++) {
  104.         int a, b, c;
  105.         scanf("%d%d%d", &a, &b, &c);
  106.         tree.add(a, b, c);
  107.     }
  108.     for (int i = 1; i <= n; i++) {
  109.         printf("%d ", tree.get_value(i));
  110.     }
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement