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
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include <utility> 

using namespace std;

vector<pair<int,int> >tab[11], miko[1000003];
int n, m, a, b, k, wynik;

void sortuj(int h)
{
	for(int j=0; j<1000003; j++)
		miko[j].clear();
	for(int j=0; j<tab[h].size(); j++)
		miko[tab[h][j].first].push_back(tab[h][j]);
	tab[h].clear();
	for(int i=0; i<1000003; i++)
	{
		for(int j=0; j<miko[i].size(); j++)
			tab[h].push_back(miko[i][j]);
	}	
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=0; i<m; i++)
	{
		cin>>a>>b>>k;
		tab[k].push_back(make_pair(a,b));
	}
	wynik=0;
	tab[3].push_back(make_pair(0,0));
	tab[3].push_back(make_pair(n+1,n+1));
	for(int i=1; i<4; i++)
	{	
		sortuj(i);
		if(tab[i].size()>0)
		{
			pair<int,int> p=tab[i][0];
			for(int j=1; j<tab[i].size(); j++)
			{
				if(p.second+1<tab[i][j].first)
				{
					tab[i+3].push_back(p);
					p=tab[i][j];
				}
				else
				{
					if(p.second<tab[i][j].second)
					{
						p.second=tab[i][j].second;
					}
				}
			}
			tab[i+3].push_back(p);
		}
	}
	for(int j=1; j<tab[6].size(); j++)
		tab[7].push_back(make_pair(tab[6][j-1].second+1, tab[6][j].first-1));
	int p4=0, p5=0, p7=0, prawy, lewy;
	while(p4<tab[4].size() && p5<tab[5].size() && p7<tab[7].size())
	{
		prawy=min(min(tab[4][p4].second, tab[5][p5].second),tab[7][p7].second);
		lewy=max(max(tab[4][p4].first, tab[5][p5].first),tab[7][p7].first);
		if(lewy<=prawy)
			wynik=wynik+prawy-lewy+1;
		if(tab[4][p4].second < tab[5][p5].second && tab[4][p4].second < tab[7][p7].second)
			p4++;
		else
		{
			if(tab[5][p5].second < tab[7][p7].second )
			p5++;
			else
			p7++;
		}
	}
	cout<<wynik<<endl;
	return 0;
}