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
#include<bits/stdc++.h>
using namespace std;

int g_t[4][1000001] = {};

struct Interval
{
	int start, end;
};

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

void mergeIntervals(vector<Interval> arr, int kol)
{
    int n = arr.size();

	// Test if the given set has at least one interval
	if (n <= 0)
		return;

	// Create an empty stack of intervals
	stack<Interval> s;

	// sort the intervals in increasing order of start time
	sort(arr.begin(), arr.end(), compareInterval);

	// push the first interval to stack
	s.push(arr[0]);

	// Start from the next interval and merge if necessary
	for (int i = 1 ; i < n; i++)
	{
		// get interval from stack top
		Interval top = s.top();

		// if current interval is not overlapping with stack top,
		// push it to the stack
		if (top.end < arr[i].start)
			s.push(arr[i]);

		// Otherwise update the ending time of top if ending of current
		// interval is more
		else if (top.end < arr[i].end)
		{
			top.end = arr[i].end;
			s.pop();
			s.push(top);
		}
	}

	// Print contents of stack
	// cout << "\n The Merged Intervals are: ";
	while (!s.empty())
	{
		Interval t = s.top();
		// cout << "[" << t.start << "," << t.end << "] ";
		for(int i=t.start; i<=t.end; ++i)
            g_t[kol][i] = 1;
		s.pop();
	}
	return;
}

int main()
{
    ios::sync_with_stdio(0);
    vector<vector<Interval>> v;
    v.resize(4);

    //freopen("in00.in", "r", stdin);
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; ++i)
    {
        int l, r, k;
        cin >> l >> r >> k;
        v[k].push_back({l,r});
    }
    mergeIntervals(v[1], 1);
    mergeIntervals(v[2], 2);
    mergeIntervals(v[3], 3);

    int res = 0;
    for(int j=1; j<=n; ++j)
        if(g_t[1][j]==1 && g_t[2][j]==1 && g_t[3][j]==0)
            res += 1;
    cout << res << endl;
}