1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

int getTreeSize (int val) {
    int exp = 1;
    while (val > 0) {
        val >>= 1;
        exp <<= 1;
    }
    return exp;
}

void update (short arr [], int left, int right, int treeLeft, int treeRight, int treeIdx, short val) {

    if (treeLeft >= left  && treeRight <= right) {
        arr[treeIdx] = arr[treeIdx] | val;
        return;
    }

    if (treeLeft > right || treeRight < left) {
        return;
    }
    int mid = (treeLeft + treeRight)/2;
    update(arr, left, right, treeLeft, mid, (treeIdx << 1) + 1, val);
    update(arr, left, right, mid + 1, treeRight, (treeIdx << 1) + 2, val);
}

int getVal (short arr [], int idx, int treeLeft, int treeRight, int treeIdx, short val) {
    if (treeLeft <= idx  && treeRight >= idx) {
        if ((arr[treeIdx] & val) == val) {
            return 1;
        }
    }

    if (treeLeft > idx || treeRight < idx) {
        return 0;
    }

    if (treeLeft == treeRight) {
        return  (arr[treeIdx] & val) == val ? 1: 0;
    }


    int mid = (treeLeft + treeRight)/2;
    int l = getVal(arr, idx, treeLeft, mid, (treeIdx << 1) + 1, val);
    int r = getVal(arr, idx, mid + 1, treeRight, (treeIdx << 1) + 2, val);
    return max(l, r);
}


int main(){
    int n, m, result, left, right, colour;
    result = 0;
    scanf("%d %d\n", &n, &m);
    int size = getTreeSize(n);
    short arr[size*2];

    for (int in = 0; in < size*2; ++in){
        arr[in] = 0;
    }


    for (int idx = 0; idx < m; ++idx) {
        scanf("%d %d %d\n", &left, &right, &colour);
        left --;
        right --;
        colour --;
        update(arr, left, right, 0, size-1, 0, (short) (1 << colour));
    }

    for (int idx = 0; idx < n; ++idx) {

        if (getVal(arr, idx, 0, size-1, 0, 1) == 0) {
            continue;
        }
        if (getVal(arr, idx, 0, size-1, 0, 2) == 0) {
            continue;
        }
        if (getVal(arr, idx, 0, size-1, 0, 4) == 1) {
            continue;
        }
        ++ result;
    }

    printf("%d\n", result);
    return 0;
}