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
/*
 * =====================================================================================
 *
 *       Filename:  kol.cpp
 *
 *    Description: https://sio2.mimuw.edu.pl/c/pa-2020-1/p/kol/
 *
 *        Version:  0.1.0
 *        Created:  07.12.2020
 *
 *         Author:  Michał Zagórski (zagura), <zagura6@gmail.com>
 *
 * =====================================================================================
 */
#include <cstdio>
#include <cinttypes>
#include <cstring>

/* Colors explanation:
 * 1 << 1 == 2
 * 1 << 2 == 4
 * 1 << 3 == 8
 * yello = 2
 * blue = 4
 * red = 8
 * white = 0
 * yellow + blue = 6 (green) <---
 * yellow + red = 10 (orange)
 * blue + red = 12 (violet)
 * yellow + blue + red = 14 (brown)
 */

constexpr uint8_t green = 6;
// last row are the numbers
constexpr size_t tree_size = 1024 * 1024 * 2;
//constexpr size_t tree_size = 16;
constexpr size_t begin0 = 0;
constexpr size_t end0 = tree_size;
inline int left(int i) {
    return 2 * i + 1;
}
inline int right(int i) {
    return 2 * i + 2;
}

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

uint8_t *tree;
void insert(int l, int r, int value, int i, int begin, int end) {
    int mid = (begin + end) / 2;
    if (end - begin < 1) {
        printf("Error");
        return;
    }
    // We have found one of right nodes
    if (l == begin and end == r + 1) {
        tree[i] |= value;
    //    printf("Range [%d:%d) insert %d\n", begin, end, value);
        return;
    }
    if (l < mid) {
        int new_end = mid;
        int new_r = r;
        if (new_end <= r + 1) {
            new_r = new_end - 1;
        }
        insert(l, new_r, value, left(i), begin, new_end);
    }
    if (r > mid - 1) {
        int new_begin = mid;
        int new_l = l;
        if (new_begin > new_l) {
            new_l = new_begin;
        }
        insert(new_l, r, value, right(i), new_begin, end);
    }
}

int count(int i, int begin, int end, int base, int n) {
    /* if (tree[i] != 0) {
        printf("Debug: b(%d), e(%d), i(%d), v(%d)\n", begin, end, i, tree[i]);
    }*/
    base |= tree[i];
    // Color doesn't match
    if ((base & (~green)) > 0) {
        //printf("\ncolor don't match %d\n", base);
        return 0;
    }
    // Numbers higher than queried n
    if (begin >= n) {
        return 0;
    }
    // Exact match and last row
    if (begin == end - 1) {
        int result = static_cast<int>(base == green);
        //printf("index: %d in %d - color: %d => %d\n", begin, i,  base, result);
        return result;
    }
    int mid = (begin + end) / 2;
    return count(left(i), begin, mid, base, n)
        + count(right(i), mid, end, base, n);
}

void print_tree(int l, int r) {
    for (int i = l; i < r; i++) {
        printf("%d ", tree[i]);
    }
}

int main() {
    int n, m;
    tree = new uint8_t[tree_size];
    std::memset(tree, 0, sizeof(uint8_t));

    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int l, r, c;
        scanf("%d %d %d", &l, &r, &c);
        l--;
        r--;
        c = 1<<c;
        insert(l, r, c, 0, 0, tree_size / 2);
    }
    int result = count(0, 0, tree_size / 2, 0, n);
    printf("%d\n", result);
//    print_tree(0, tree_size - 1);
    return 0;
}