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

struct S {
  S(int start, int len) : start(start), len(len) {}

  bool contains(int p) const {
    if (p >= start && p <= start + len) {
      return true;
    }
    return false;
  }

  bool operator<(const S &other) const { return start < other.start; }

  int start{0};
  int len{0};
};

std::set<S> concat(const std::multiset<S> &s) {
  std::set<S> result;

  if (s.empty()) {
    return result;
  }

  S current = *(s.begin());

  for (const auto &i : s) {
    if (current.start == i.start) {
      current.len = std::max(current.len, i.len);
    } else if (current.start + current.len >= i.start) {
      current.len = std::max(current.len, i.start - current.start + i.len);
    } else {
      result.insert(current);
      current = i;
    }
  }

  result.insert(current);
  return result;
}

bool contains(int p, const std::set<S> &s) {
  if (s.empty()) {
    return false;
  }

  auto iter = std::upper_bound(s.begin(), s.end(), S(p, 0));
  if (iter == s.begin()) {
    return false;
  }

  return (--iter)->contains(p);
}

void print(const std::set<S> &s) {
  for (const auto &i : s) {
    fprintf(stderr, "[%d %d], ", i.start, i.len);
  }
  fprintf(stderr, "\n");
}

void test() {
  // TODO: ...
}

int main() {
  // DEBUG
  //  test();
  //  return 0;
  // DEBUG

  int N = 0;
  int M = 0;

  std::cin >> N;
  std::cin >> M;

  std::vector<std::multiset<S>> v = {std::multiset<S>(), std::multiset<S>(),
                                     std::multiset<S>()};

  for (int i = 0; i < M; ++i) {
    int l = 0, r = 0, k = 0;

    std::cin >> l;
    std::cin >> r;
    std::cin >> k;

    v[k - 1].insert(S(l, r - l));
  }

  //
  std::set<S> yellow = concat(v[0]);
  std::set<S> blue = concat(v[1]);
  std::set<S> red = concat(v[2]);

  // DEBUG
  //  print(yellow);
  //  print(blue);
  //  print(red);
  // DEBUG

  int sum = 0;

  for (int i = 1; i <= N; ++i) {
    if (contains(i, yellow) && contains(i, blue) && !contains(i, red)) {
      sum++;
    }
  }

  std::cout << sum << std::endl;
  return 0;
}