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

using namespace std;

const int ZOLTY = 0;
const int NIEBIESKI = 1;
const int CZERWONY = 2;

using zakres = pair< int, int >;

struct Tresc
{
	int lpusz;
	vector< zakres > kolory[3];
};

void porzadkuj(vector< zakres >& kolor ) {
	sort(kolor.begin(), kolor.end(), [](zakres const& a, zakres const& b) {
		return a.first < b.first;
	});
}

vector< zakres > scalaj( vector< zakres > kolor ) {
	vector< zakres > wynik;

	for(auto&& z : kolor) {
		if (wynik.size() == 0) {
			wynik.push_back(z);
		}
		else {
			if(z.first <= wynik.back().second) {
				wynik.back().second = max(wynik.back().second, z.second);
			}
			else {
				wynik.push_back(z);
			}
		}
	}
	return wynik;
}

vector< zakres > odwroc( vector< zakres > kolor, int koniec ) {
	vector< zakres > wynik;
	int pocz = 0;
	
	for( auto&& z : kolor ) {
		if(pocz < z.first) {
			wynik.push_back({pocz, z.first});
		}
		pocz = z.second;
	}

	if( pocz < koniec ) {
		wynik.push_back({pocz, koniec});
	}

	return wynik;
}

int zlicz( vector< zakres > const& kolor) {
	int wynik = 0;
	for( auto&& z : kolor ) {
		wynik += z.second - z.first;
	}
	return wynik;
}

int main() {
	Tresc tresc;
	ios::sync_with_stdio(false);
	int lop; cin >> tresc.lpusz >> lop;

	for (int i = 0; i < lop; ++i ) {
		int pocz, kon, kolor1; cin >> pocz >> kon >> kolor1;
		// liczymy od 0 a nie od 1; kon zostaje bez zmian, zeby wskazywac ZA
		tresc.kolory[kolor1 - 1].push_back({pocz - 1, kon});
	}

	for (int i = 0; i <= 2; ++i) {
		porzadkuj(tresc.kolory[i]);
	}

	vector< zakres > czerwone = scalaj(tresc.kolory[CZERWONY]);
	vector< zakres > bezzolte = odwroc(scalaj(tresc.kolory[ZOLTY]), tresc.lpusz);
	vector< zakres > bezniebieskie = odwroc(scalaj(tresc.kolory[NIEBIESKI]), tresc.lpusz);

	vector< zakres > zle;
	zle.reserve(czerwone.size() + bezzolte.size() + bezniebieskie.size() );
	copy( czerwone.begin(), czerwone.end(), back_inserter(zle));
	copy( bezzolte.begin(), bezzolte.end(), back_inserter(zle));
	copy( bezniebieskie.begin(), bezniebieskie.end(), back_inserter(zle));

	porzadkuj(zle);
	vector< zakres> dobre = odwroc( scalaj(zle), tresc.lpusz);
	cout << zlicz(dobre) << endl;
}