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

using namespace std;

#define BLUE 2
#define YELLOW 1
#define RED 3
#define LEAF 4
#define COR 5
#define LEFT 6
#define RIGHT 7

#define N 1000000

int tree[N + 30][8];

int parent(int me) {
    return (me - 1) / 2;
}

int left_child(int me) {
    return 2 * me + 1;
}

int right_child(int me) {
    return 2 * me + 2;
}

void paint(int me, int color, int border_left, int border_right) {
    if (border_left <= tree[me][LEFT] && tree[me][RIGHT] <= border_right) {
        tree[me][color] = 1;
        return;
    }
    if ( 
        (border_left >= tree[me][LEFT] && border_left < tree[me][RIGHT]) ||
        (border_right >= tree[me][LEFT] && border_right < tree[me][RIGHT]) 
    ) {
        paint(left_child(me), color, border_left, border_right);
        paint(right_child(me), color, border_left, border_right);
    }
}

void interv(int me, int left, int right) {
    tree[me][LEFT] = left;
    tree[me][RIGHT] = right;

    if (!tree[me][LEAF]) {
        interv(left_child(me), left, (left + right) / 2);
        interv(right_child(me), (left + right) / 2, right);
    }
}

void ct (int me, bool blue, bool yellow, bool red, int &c) {
    red = red || tree[me][RED];
    yellow = yellow || tree[me][YELLOW];
    blue = blue || tree[me][BLUE];

    if (tree[me][LEAF] && tree[me][COR] && blue && yellow && !red) {
        c++;
    }

    if (!tree[me][LEAF]) {
        ct(left_child(me), blue, yellow, red, c);
        ct(right_child(me), blue, yellow, red, c);
    }
}

int main() {
    ios_base::sync_with_stdio(false);

    int n, m;

    cin >> n >> m;

    int l = log2(n);

    int full_leaves = pow(2, l);


    if (full_leaves < n) {
        full_leaves *= 2;
    }

    for (int i = 0; i < full_leaves; i++) {
        tree[full_leaves - 1 + i][LEAF] = 1;
        if (i < n) {
            tree[full_leaves - 1 + i][COR] = 1;
        }
    }

    interv(0, 0, full_leaves);

    for (int i = 0; i < m; i++) {
        int l, r , k;
        cin >> l >> r >> k;
        paint(0, k, l, r + 1);
    }

    int c = 0;

    ct(0, false, false, false, c);

    cout << c;
    
    return 0;
}