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
#include <stdio.h>
#include <stdlib.h>

#define MAX_NM 1000*1010

struct DATA {
  int l, r, k;
};
struct DATA in[MAX_NM];
int n, m;
int c[MAX_NM+1];

int compare_asc(const void *arg1, const void *arg2) {
  return (((struct DATA *)arg1)->l - ((struct DATA *)arg2)->l);
}

int next_int;
int has_next(int kol) {
  for(int i = next_int+1; i < m; i++) {
    if(in[i].k == kol) {
      next_int = i;
      return 1;
    }
  }
  return 0;
}
int get_next() {
  return next_int;
}

void iterate(int kol, int step) {
//  printf("iterate: %d %d\n", kol, step); fflush(stdout);
  int idx = -1;
  next_int = -1;
  while(has_next(kol) && idx < n) {
    int next = get_next();
//    printf("next=%d; kol=%d\n", next, kol); fflush(stdout);
    int from = in[next].l;
    int to = in[next].r;
    while(idx < to) {
      idx++;
      if (from <= idx && idx <= to) {
        c[idx] += step;
      }
    }
  }
}

int main() {
  // Read data and initialize tables
  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; i++) {
    c[i] = 0;
  }
  for(int i = 0; i < m; i++) {
    scanf("%d %d %d", &(in[i].l), &(in[i].r), &(in[i].k));
  }

//  printf("sort\n"); fflush(stdout);

  // Sort input by left edge
  qsort(in, m, sizeof(*in), compare_asc);
  // Iterate for yellow (c[i]++)
  iterate(1, 1);
  // TODO: iterate for blue (c[i]++)
  iterate(2, 1);
  // TODO: iterate for red (c[i] += 3)
  iterate(3, 3);

//  printf("in:\n");
//  for(int i = 0; i < m; i++) {
//    printf("[%d]: %d %d %d\n", i, in[i].l, in[i].r, in[i].k);
//  }
  // Count green paint cans
  // (0 - white; 1 - yellow/blue; 2 - green; other - other color)
  int ret = 0;
  for (int i = 1; i <= n; i++) {
//    printf("[%d]=%d, ", i, c[i]);
    if (c[i] == 2) {
      ret++;
    }
  }
  printf("%d", ret);
  return 0;
}