Greg and Array (Codeforces 296C)
Tags: Implement, data structures

Greg has an array a = a1, a2, ..., an and m operations. Each operation looks as: li, ri, di, (1 ≤ li ≤ ri ≤ n). To apply operation i to the array means to increase all array elements with numbers li, li + 1, ..., ri by value di.Greg wrote down k queries on a piece of paper. Each query has the following form: xi, yi, (1 ≤ xi ≤ yi ≤ m). That means that one should apply operations with numbers xi, xi + 1, ..., yi to the array.Now Greg is wondering, what the array a will be after all the queries are executed. Help Greg.

Input: The first line contains integers n, m, k (1 ≤ n, m, k ≤ 105). The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 105) — the initial array.Next m lines contain operations, the operation number i is written as three integers: li, ri, di, (1 ≤ li ≤ ri ≤ n), (0 ≤ di ≤ 105).Next k lines contain the queries, the query number i is written as two integers: xi, yi, (1 ≤ xi ≤ yi ≤ m).The numbers in the lines are separated by single spaces.

Output: On a single line print n integers a1, a2, ..., an — the array after executing all the queries. Separate the printed numbers by spaces.Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams of the %I64d specifier.


Sample Inputs:
3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3

1 1 1
1
1 1 1
1 1

4 3 6
1 2 3 4
1 2 1
2 3 2
3 4 4
1 2
1 3
2 3
1 2
1 3
2 3

Sample Outputs:
9 18 17

2

5 18 31 20

Solution (Python):
import sys
input_fn = sys.stdin.readline
print_fn = sys.stdout.write
N = 100002
(n, m, k) = map(int, input_fn().split())
lista = list(map(int, input_fn().split()))
inc = [0] * (n + 2)
op_ac = [0] * (m + 2)
op = [(0, 0, 0)]

def process_op():
    (a, b, c) = map(int, input_fn().split())
    op.append((a, b, c))

def process_k():
    (a, b) = map(int, input_fn().split())
    op_ac[a] += 1
    op_ac[b + 1] -= 1

def update_inc():
    for i in range(1, m + 1):
        op_ac[i] += op_ac[i - 1]
        inc[op[i][0]] += op[i][2] * op_ac[i]
        inc[op[i][1] + 1] -= op[i][2] * op_ac[i]

def update_lista():
    for i in range(1, n + 1):
        inc[i] += inc[i - 1]
        lista[i - 1] += inc[i]
for _ in range(m):
    process_op()
for _ in range(k):
    process_k()
update_inc()
update_lista()
print_fn(' '.join(map(str, lista)) + '\n')

Solution (Python):
import sys
input_fn = sys.stdin.readline
print_fn = sys.stdout.write
N = 100002
(n, m, k) = map(int, input_fn().split())
lista = list(map(int, input_fn().split()))
inc = [0] * (n + 2)
op_ac = [0] * (m + 2)
op = [(0, 0, 0)]

def process_op():
    (a, b, c) = map(int, input_fn().split())
    op.append((a, b, c))

def process_k():
    (a, b) = map(int, input_fn().split())
    op_ac[a] += 1
    op_ac[b + 1] -= 1

def update_inc():
    for i in range(1, m + 1):
        op_ac[i] += op_ac[i - 1]
        inc[op[i][0]] += op[i][2] * op_ac[i]
        inc[op[i][1] + 1] -= op[i][2] * op_ac[i]

def update_lista():
    for i in range(1, n + 1):
        inc[i] += inc[i - 1]
        lista[i - 1] += inc[i]
for _ in range(m):
    process_op()
for _ in range(k):
    process_k()
update_inc()
update_lista()
print_fn(' '.join(map(str, lista)) + '\n')

Solution (Python):
import sys
input = sys.stdin.readline
print = sys.stdout.write
N = 100002
(n, m, k) = map(int, input().split())
lista = list(map(int, input().split()))
inc = [0] * (n + 2)
op_ac = [0] * (m + 2)
op = [(0, 0, 0)]
for i in range(1, m + 1):
    (a, b, c) = map(int, input().split())
    op.append((a, b, c))
for _ in range(k):
    (a, b) = map(int, input().split())
    op_ac[a] += 1
    op_ac[b + 1] -= 1
for i in range(1, m + 1):
    op_ac[i] += op_ac[i - 1]
    inc[op[i][0]] += op[i][2] * op_ac[i]
    inc[op[i][1] + 1] -= op[i][2] * op_ac[i]
for i in range(1, n + 1):
    inc[i] += inc[i - 1]
    lista[i - 1] += inc[i]
print(' '.join(map(str, lista)) + '\n')