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

using namespace std;

struct farba
{
    int c, // kolor
     x,    // pozycja
     t;   // typ - 0 start, 1 end
};

bool sortfarba(const farba &a, const farba &b) { return
    (a.x < b.x) || (a.x == b.x && a.t < b.t)|| (a.x == b.x && a.t == b.t && a.c > b.c); 
}


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

    int n, m;
    cin >> n >> m;
    farba *f = new farba[2*m];
    for (int i=0;i<m;i++) {
        int l,r,k;
        cin >> l >> r >> k;
        f[2*i].c = k;
        f[2*i].x = l;
        f[2*i].t = 0;
        f[2*i+1].c = k;
        f[2*i+1].x = r;
        f[2*i+1].t = 1;
    }
    sort(f, f+2*m, sortfarba);
    int s[4] { 0 };
    int l = -1;
    int r = 0;
    for (int i=0;i<2*m;i++) {
        if (f[i].t == 0) {
            s[f[i].c]++;
            bool ok = s[1] > 0 && s[2] > 0 && s[3] == 0;
            if ((f[i].c == 3) && l>0) {
               r += (f[i].x - l);
               l = -1;
            }
            if (l == -1 && ok) l = f[i].x;
            if (!ok) l = -1;

        } else {
            s[f[i].c]--;
            bool ok = s[1] > 0 && s[2] > 0 && s[3] == 0;
            if (f[i].c == 3 && ok) {
                l = f[i].x+1;
            } else {
                if (l>0 && !ok) {
                    r += (f[i].x - l + 1);
                    l = -1;
                }
            }
        }

    }
    cout << r << '\n';
}