Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- using namespace std;
- int ps[300000], pe[300000], pc[300000] = { 0 };
- int max(int a, int b) {
- if (a>b)return a;
- return b;
- }
- int min(int a, int b) {
- if (a<b)return a;
- return b;
- }
- void init(int p, int s, int e) {
- int m = (s + e) / 2;
- ps[p] = s;
- pe[p] = e;
- if (s >= e)return;
- init(p * 2 + 1, s, m);
- init(p * 2 + 2, m + 1, e);
- }
- void add(int p, int s, int e, int v) {
- if (ps[p] == s&&pe[p] == e) {
- pc[p] += v;
- return;
- }
- if (s <= pe[p * 2 + 1])add(p * 2 + 1, s, min(e, pe[p * 2 + 1]), v);
- if (e >= ps[p * 2 + 2])add(p * 2 + 2, max(s, ps[p * 2 + 2]), e, v);
- }
- int get(int p, int a) {
- if (ps[p] == pe[p])return pc[p];
- if (a<ps[p * 2 + 2])return get(p * 2 + 1, a) + pc[p];
- return get(p * 2 + 2, a) + pc[p];
- }
- int main() {
- int n, i, a, b, c, s = 0;
- scanf("%d", &n);
- init(0, 0, n);
- for (i = 0; i <= n; i++) {
- scanf("%d%d%d", &a, &b, &c);
- add(0, a, b, c);
- }
- for (i = 1; i <= n; i++)
- printf("%d ", get(0, i));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement