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
#include <bits/stdc++.h>
using namespace std;

//vector <long long> v;

//stack <long long> s, s2;
//bbbbaaaa
//queue <long long> s, s2;

long long int  z[1000000], x[3][1000001][2], y[10], m, szu, wy[10][1];
//char s[1000000], c;

int war(const void*a, const void *b)
{
    if(*(long long*)a>*(long long*)b)return(1);
    return(0);
}

int main()
{
    long long int c, d, e, f, g, i, j, q, t, k, a, n, b, w, p, aa, bb, cc, dd, nn, kk;

    t=1;
    //scanf("%lld", &t);
    for(q=1; q<=t; q++)
    {
        scanf("%lld%lld", &n, &m);

        x[0][m][0]=1000006;
        x[0][m][1]=1000006;
        x[1][m][0]=1000006;
        x[1][m][1]=1000006;
        x[2][m][0]=1000006;
        x[2][m][1]=1000006;


        for(i=0; i<m; i++)
        {
            scanf("%lld%lld%lld", &b, &c, &a);
            x[a-1][i][0]=b-1;
            x[a-1][i][1]=c-1;
            x[a%3][i][0]=1000006;
            x[a%3][i][1]=1000006;
            x[(a+1)%3][i][0]=1000006;
            x[(a+1)%3][i][1]=1000006;
        }


        qsort(x[0], m, 16, war);
        qsort(x[1], m, 16, war);
        qsort(x[2], m, 16, war);


        w=0;
        a=-1;
        b=-1;
        c=-1;
        aa=0;
        bb=0;
        cc=0;
        for(i=0; i<n; i++)
        {
            while(x[0][aa][0]<=i)
            {
                a=max(a, x[0][aa][1]);
                aa++;
            }
            while(x[1][bb][0]<=i)
            {
                b=max(b, x[1][bb][1]);
                bb++;
            }
            while(x[2][cc][0]<=i)
            {
                c=max(c, x[2][cc][1]);
                cc++;
            }

            if(a>=i && b>=i && c<i)w++;
        }

        printf("%lld\n", w);
    }

    return(0);
}