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

using namespace std;

struct Interval
{
	int start;
	int end;
	Interval() : start(0), end(0)
	{
	}
	Interval(int s, int e) : start(s), end(e)
	{
	}
};

bool compareInterval(Interval i1, Interval i2)
{
	return (i1.start < i2.start);
}

vector<Interval> merge_intervals(vector<Interval> &intervals)
{
	vector<Interval> result_set;
	if (intervals.empty())
		return result_set;

	sort(intervals.begin(), intervals.end(), compareInterval);
	result_set.push_back(intervals[0]);

	for (int i = 1; i < intervals.size(); i++)
	{
		if (result_set.back().end < intervals[i].start)
			result_set.push_back(intervals[i]);
		else
			result_set.back().end = max(result_set.back().end, intervals[i].end);
	}
	return result_set;
}

vector<Interval> intersectIntervals(vector<Interval> &arr1,	vector<Interval> &arr2)
{
	vector<Interval> result_set;
	int i = 0, j = 0;

	int n = arr1.size(), m = arr2.size();

	while (i < n && j < m) {
		int l = max(arr1[i].start, arr2[j].start);
		int r = min(arr1[i].end, arr2[j].end);

		if (l <= r)
			result_set.push_back(Interval(l, r));

		if (arr1[i].end < arr2[j].end)
			i++;
		else
			j++;
	}
	return result_set;
}


int main()
{
	vector<Interval> zolty,czerwony, niebieski;

	int n, m;
	cin >> n >> m;
	std::vector<int> puszki(n+1);
	int rV = 0;
	int l, r, k;

	for (int mi = 0; mi < m; mi++)
	{
		cin >> l >> r >> k;
		if (k == 1)
			zolty.push_back(Interval(l, r));
		if (k == 2)
			niebieski.push_back(Interval(l, r));
		if (k == 3)
			czerwony.push_back(Interval(l, r));
	}

	zolty = merge_intervals(zolty);
	niebieski = merge_intervals(niebieski);
	czerwony = merge_intervals(czerwony);

	vector<Interval> zielony = intersectIntervals(zolty, niebieski);

	for (int i = 0; i < czerwony.size(); i++)
		for (int p = czerwony[i].start; p <= czerwony[i].end; p++)
			puszki[p]=100;

	for (int i = 0; i < zielony.size(); i++)
		for (int p = zielony[i].start; p <= zielony[i].end; p++)
			if (puszki[p] != 100)
				rV++;

	cout << rV << endl;
    return 0;
}