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


struct Interval 
{ 
    int start, end; 
}; 
  

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

void mergeIntervals(vector<Interval> arr, int n,int ans[]) 
{ 
     
    if (n <= 0) 
        return; 
  

    stack<Interval> s; 
  
    sort(arr.begin(), arr.end(), compareInterval); 
  
    s.push(arr[0]); 
  
    for (int i = 1 ; i < n; i++) 
    { 
        Interval top = s.top(); 
  
        
        if (top.end < arr[i].start) 
            s.push(arr[i]); 
  
      
        else if (top.end < arr[i].end) 
        { 
            top.end = arr[i].end; 
            s.pop(); 
            s.push(top); 
        } 
    } 
  

    while (!s.empty()) 
    { 
        Interval t = s.top(); 
        for(int i = t.start;i<=t.end;i++)
        	ans[i] = 1;
        s.pop(); 
    } 
    return; 
} 
  
int x,y,z,n,m,ans1[MAXN],ans2[MAXN],ans3[MAXN],odp = 0; 
int main() 
{ 
      vector<Interval> v1,v2,v3;
      
    cin>>n>>m;
    for(int i = 0;i<m;i++)    
	{
    	cin>>x>>y>>z;
		if(z == 1)    	
    		v1.push_back({x,y});
    	else if(z == 2)
    		v2.push_back({x,y});
    	else if(z == 3)
    		v3.push_back({x,y});
	}
    
    mergeIntervals(v1,v1.size(),ans1);
    mergeIntervals(v2,v2.size(),ans2);
    mergeIntervals(v3,v3.size(),ans3);
    
    
    	
	for(int i = 0;i<=n;i++)
		{
			if(ans1[i] == 1 && ans2[i] == 1 && ans3[i] == 0)
				odp++;
		}
    
    cout<<odp<<endl;
    
    
    return 0; 
}