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
#include <iostream>
#include <vector>

using namespace std;

struct Node {
    vector<Node *> children;
    int from;
    int to;
    int color;

    Node() : children({}), from(0), to(0), color(0) {}

    Node(int _from, int _to, int _color) : children({}), from(_from), to(_to), color(_color) {}
};

void updateTree(Node *node, int from, int to, int color) {
    if (node->from > to || node->to < from) {
        return;
    }

    if (node->children.empty()) {
        int newColor = (node->color | color);
        if (newColor != node->color) {
            if (node->from < from) {
                node->children.push_back(new Node(node->from, from - 1, node->color));
            }

            node->children.push_back(new Node(max(from, node->from), min(to, node->to), newColor));

            if (node->to > to) {
                node->children.push_back(new Node(to + 1, node->to, node->color));
            }

        }
    } else {
        for (Node *child : node->children) {
            updateTree(child, from, to, color);
        }
    }
}

int calculate(Node *node, int color) {
    if (node->children.empty()) {
        if (node->color == color) {
            return node->to - node->from + 1;
        }
        return 0;
    }

    int sum = 0;
    for (auto child : node->children) {
        sum += calculate(child, color);
    }

    return sum;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int count;
    int ops;
    cin >> count >> ops;

    auto root = new Node();
    root->from = 0;
    root->to = count + 1;

    for (int i = 0; i < ops; i++) {
        int from, to, color;
        cin >> from >> to >> color;
        auto colorCode = (1 << color);
        updateTree(root, from, to, colorCode);
    }

    auto yellow = (1 << 1);
    auto blue = (1 << 2);
    auto green = (yellow | blue);
    cout << calculate(root, green);

    return 0;
}