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

using namespace std;

pair<int, int> ops[2 * 1024 * 1024];

int main() {
	ios_base::sync_with_stdio(0);

	int cans_ct, ops_ct;
	cin >> cans_ct >> ops_ct;

	int begin, end, color;
	for (int i = 0; i < ops_ct; ++i) {
		cin >> begin >> end >> color;

		ops[2 * i] = { begin, color };
		ops[2 * i + 1] = { end + 1, -1 * color };
	}

	sort(ops, ops + 2 * ops_ct);

	int result = 0;
	int prev = ops[0].first - 1;
	int colors[4] = {};
	for(int i = 0; i < 2 * ops_ct;){
		int pt = ops[i].first;

		if(colors[1] > 0 && colors[2] > 0 && colors[3] == 0){
			result += pt - prev;
		}
		prev = pt;

		while(i < 2 * ops_ct && pt == ops[i].first){
			if(ops[i].second > 0){
				++colors[ops[i].second];
			} else {
				--colors[-1 * ops[i].second];
			}
			++i;
		}
	}

	cout << result << endl;

	return 0;
}