Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2019
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. int ps[300000], pe[300000], pc[300000] = { 0 };
  8.  
  9. int max(int a, int b) {
  10.     if (a>b)return a;
  11.     return b;
  12. }
  13. int min(int a, int b) {
  14.     if (a<b)return a;
  15.     return b;
  16. }
  17.  
  18. void init(int p, int s, int e) {
  19.     int m = (s + e) / 2;
  20.     ps[p] = s;
  21.     pe[p] = e;
  22.     if (s >= e)return;
  23.     init(p * 2 + 1, s, m);
  24.     init(p * 2 + 2, m + 1, e);
  25. }
  26.  
  27. void add(int p, int s, int e, int v) {
  28.     if (ps[p] == s&&pe[p] == e) {
  29.         pc[p] += v;
  30.         return;
  31.     }
  32.     if (s <= pe[p * 2 + 1])add(p * 2 + 1, s, min(e, pe[p * 2 + 1]), v);
  33.     if (e >= ps[p * 2 + 2])add(p * 2 + 2, max(s, ps[p * 2 + 2]), e, v);
  34. }
  35.  
  36. int get(int p, int a) {
  37.     if (ps[p] == pe[p])return pc[p];
  38.     if (a<ps[p * 2 + 2])return get(p * 2 + 1, a) + pc[p];
  39.     return get(p * 2 + 2, a) + pc[p];
  40. }
  41.  
  42. int main() {
  43.     int n, i, a, b, c, s = 0;
  44.     scanf("%d", &n);
  45.     init(0, 0, n);
  46.     for (i = 0; i <= n; i++) {
  47.         scanf("%d%d%d", &a, &b, &c);
  48.         add(0, a, b, c);
  49.     }
  50.     for (i = 1; i <= n; i++)
  51.         printf("%d ", get(0, i));
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement