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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> nieb;
vector<pair<int, int>> z;
vector<pair<int, int>> cz;
vector<pair<int, int>> niebieski;
vector<pair<int, int>> zolty;
vector<pair<int, int>> czerwony;
bool comp(pair<int, int> a, pair<int, int> b)
{
    if ((b.first - 1 >= a.first && (b.first - 1 <= a.second)) || (a.first - 1 >= b.first && (a.first - 1 <= b.second)) || a.first == b.first || a.first == b.second || b.first == a.first || b.first == a.second)
        return true;
    else
    {
        return false;
    }
}
bool binarySearch(vector<pair<int, int>> tab, int x)
{
    int l = 0;
    int r = tab.size() - 1;
    while (l <= r)
    {
        int m = (l + r) / 2; 
        if (tab[m].first <= x && tab[m].second >= x)
        {
                return true;
        }
        if (tab[m].first > x)
            r = m - 1;
        else if (tab[m].second < x) 
            l = m + 1;
    }
    return false;
}
int n, m, a, b, k;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b >> k;
        --a;
        --b;
        if (k == 2)
            niebieski.push_back(make_pair(a, b));
        else if (k == 1)
            zolty.push_back(make_pair(a, b));
        else if (k == 3)
            czerwony.push_back(make_pair(a, b));
    }
    pair<int, int> p;
    if (niebieski.size())
    {
        sort(niebieski.begin(), niebieski.end());
        p = niebieski[0];
        for (int i = 1; i < niebieski.size(); ++i)
        {
            if (comp(niebieski[i], p))
                p = make_pair(min(niebieski[i].first, p.first), max(niebieski[i].second, p.second));
            else
            {
                nieb.push_back(p);
                p = niebieski[i];
            }
        }
        nieb.push_back(p);
    }
    //zolty
    if (zolty.size())
    {
        sort(zolty.begin(), zolty.end());
        p = zolty[0];
        for (int i = 1; i < zolty.size(); ++i)
        {
            if (comp(zolty[i], p))
                p = make_pair(min(zolty[i].first, p.first), max(zolty[i].second, p.second));
            else
            {
                z.push_back(p);
                p = zolty[i];
            }
        }
        z.push_back(p);
    }
    //czerwony
    if (czerwony.size())
    {
        sort(czerwony.begin(), czerwony.end());
        p = czerwony[0];
        for (int i = 1; i < czerwony.size(); ++i)
        {
            if (comp(czerwony[i], p))
                p = make_pair(min(czerwony[i].first, p.first), max(czerwony[i].second, p.second));
            else
            {
                cz.push_back(p);
                p = czerwony[i];
            }
        }
        cz.push_back(p);
    }
    // sort(z.begin(), z.end());
    // sort(nieb.begin(), nieb.end());
    // sort(cz.begin(), cz.end());
    // for (auto i : nieb)
    //     cout << "nieb: " << i.first << " " << i.second << endl;
    // for (auto i : z)
    //     cout << "z: " << i.first << " " << i.second << endl;
    // for (auto i : cz)
    //     cout << "cz: " << i.first << " " << i.second << endl;
    int wynik = 0;
    for (int i = 0; i < n; ++i)
    {
        //cout << i << ": ";
        if (cz.size())
        {
            if (binarySearch(cz, i) == true)
            {
                //cout << "czerwony\n";
                continue;
            }
        }

        if (z.size() && nieb.size())
        {
            if (binarySearch(z, i) == true)
            {
                //cout << " zolty ";
                if (binarySearch(nieb, i) == true)
                {
                    //cout << i << endl;
                    ++wynik;
                    //cout << "niebieski";
                }
            }
        }
        //cout << endl;
    }
    cout << wynik << '\n';
}