Interesting Array (Codeforces 483D)
Tags: Others, data structures

We'll call an array of n non-negative integers a[1], a[2], ..., a[n] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1 ≤ li ≤ ri ≤ n) meaning that value  should be equal to qi. Your task is to find any interesting array of n elements or state that such array doesn't exist.Expression x&y means the bitwise AND of numbers x and y. In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".

Input: The first line contains two integers n, m (1 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of elements in the array and the number of limits.Each of the next m lines contains three integers li, ri, qi (1 ≤ li ≤ ri ≤ n, 0 ≤ qi < 230) describing the i-th limit.

Output: If the interesting array exists, in the first line print "YES" (without the quotes) and in the second line print n integers a[1], a[2], ..., a[n] (0 ≤ a[i] < 230) decribing the interesting array. If there are multiple answers, print any of them.If the interesting array doesn't exist, print "NO" (without the quotes) in the single line.


Sample Inputs:
3 1
1 3 3

3 2
1 3 3
1 3 2

Sample Outputs:
YES
3 3 3

NO

Solution (Python):
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = []
for _ in range(m):
    (l, r, q) = map(int, input().split())
    l -= 1
    r -= 1
    a.append((l, r, q))
res = [0] * n
bad = False
for i in range(30):
    events = [0] * (n + 1)
    for (l, r, q) in a:
        if q & 1 << i:
            events[l] += 1
            events[r + 1] -= 1
    c = 0
    for j in range(n):
        c += events[j]
        if c > 0:
            res[j] |= 1 << i
    s = [0] * (n + 1)
    for j in range(n):
        s[j + 1] = s[j] + (res[j] >> i & 1)
    for (l, r, q) in a:
        if q & 1 << i == 0:
            if s[r + 1] - s[l] == r - l + 1:
                bad = True
                break
if bad:
    print('NO')
else:
    print('YES')
    print(*res)

Solution (Python):
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = []
for _ in range(m):
    (l, r, q) = map(int, input().split())
    l -= 1
    r -= 1
    a.append((l, r, q))
res = [0] * n
bad = False
for i in range(30):
    events = [0] * (n + 1)
    for (l, r, q) in a:
        if q & 1 << i:
            events[l] += 1
            events[r + 1] -= 1
    c = 0
    for j in range(n):
        c += events[j]
        if c > 0:
            res[j] |= 1 << i
    s = [0] * (n + 1)
    for j in range(n):
        s[j + 1] = s[j] + (res[j] >> i & 1)
    for (l, r, q) in a:
        if q & 1 << i == 0:
            if s[r + 1] - s[l] == r - l + 1:
                bad = True
                break
if bad:
    print('NO')
else:
    print('YES')
    print(*res)

Solution (Python):
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = []
for _ in range(m):
    (l, r, q) = map(int, input().split())
    l -= 1
    r -= 1
    a.append((l, r, q))
res = [0] * n
bad = False
for i in range(30):
    events = [0] * (n + 1)
    for (l, r, q) in a:
        if q & 1 << i:
            events[l] += 1
            events[r + 1] -= 1
    c = 0
    for j in range(n):
        c += events[j]
        if c > 0:
            res[j] |= 1 << i
    s = [0] * (n + 1)
    for j in range(n):
        s[j + 1] = s[j] + (res[j] >> i & 1)
    for (l, r, q) in a:
        if q & 1 << i == 0:
            if s[r + 1] - s[l] == r - l + 1:
                bad = True
                break
if bad:
    print('NO')
else:
    print('YES')
    print(*res)