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
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;

int n,m;
int s,e,color;

struct triplet {
	int index;
	bool isStart;
	int color; 
};

struct can {
	bool changesState = false;
	int colors[4] = { 0 }; 
};

triplet changes[2000002];
can cans[1000002];


bool compare(const triplet &a, const triplet &b) {
	return a.index < b.index;
}

string kolory(int color) {
	if (color == 1 ) return "zolty";
	if (color == 2 ) return "niebieski";
	if (color == 3 ) return "czerwony";
	return "";
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i=0; i<m;i++) {
		scanf("%d %d %d", &s, &e, &color);
		triplet t1,t2;
		t1.index = s;
		t1.isStart = true;
		t1.color = color;
		t2.index = e + 1;
		t2.isStart = false;
		t2.color = color;

		changes[2*i] = t1;
		changes[2*i + 1] = t2;
	}

	sort(changes, changes + (2*m), compare);

	// for (int i=0; i<2*m; i++) {
	// 	printf("%d %s %s\n", changes[i].index, changes[i].isStart ? "in  " : "out ", 
	// 		kolory(changes[i].color).c_str());
	// }

	can previous;
	previous.changesState = true; 

	for (int i=0; i<2*m; i++) {
		triplet change = changes[i];
		if (!cans[change.index].changesState) {
			cans[change.index] = previous;
		}
		if (change.isStart) {
			cans[change.index].colors[change.color]++;
		} else {
			cans[change.index].colors[change.color]--;
		}
		previous = cans[change.index];
	}

	// for (int i=1;i<=n;i++) {
	// 	printf("puszka %d %s zolty:%d niebieski:%d czerwony:%d \n", i, cans[i].changesState ? "Y " : "N ",
	// 		cans[i].colors[1], cans[i].colors[2], cans[i].colors[3]);
	// }

	int count = 0;
	bool prevGreen = false;
	for (int i=1;i<=n;i++) {
		if(!cans[i].changesState && prevGreen) count++;
		else if (cans[i].changesState) {
			if (cans[i].colors[1] > 0 && cans[i].colors[2] > 0 && cans[i].colors[3] == 0) { 
				count++;
				prevGreen = true;
			} else {
				prevGreen = false;
			}
		}
	}

	printf("%d\n", count);

	return 0;
}