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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <algorithm>
#include <vector>

#define FOR(name, j)  for(int name = 0; name <  (j); name++)
#define MAX(a,b)      ((a) > (b) ? (a) : (b))
#define MIN(a,b) 	  ((a) < (b) ? (a) : (b))
#define checkbit(n,b) ((n >> b) & 1)
#define INF           (int)1e9
#define ll 			  long long

using namespace std;

enum PointType {
	BEGGINING,
	END
};

enum Color {
	RED, 
	YELLOW, 
	BLUE
};

struct Point {
	int pos;
	PointType type;
	Color color;

	bool operator < (const Point other) {
		if(pos != other.pos) {
		return pos < other.pos;
	} else {
		return type == BEGGINING;
	}
	}
};

struct CanCounter {
	int yellow = 0;
	int blue = 0;
	int red = 0;
};

Color numToColor(int num) {
	switch (num) {
		case 1:
			return YELLOW;
		case 2:
			return BLUE;
		case 3:
			return RED;
	}
}

vector<Point> loadPoints(int numOperations) {
	vector<Point> points(numOperations * 2);

	int j = 0;
	for(int i = 0; i < numOperations; i++) {
		int x1, x2, col;
		scanf("%i %i %i", &x1, &x2, &col);

		Color color = numToColor(col);

		Point p1 = {
			x1,
			BEGGINING,
			color
		};

		Point p2 = {
			x2,
			END,
			color
		};

		points[j] = p1;
		j++;
		points[j] = p2;
		j++;
	}

	return points;
}

bool comparePoints(const Point& p1, const Point& p2) {
	if(p1.pos != p2.pos) {
		return p1.pos < p2.pos;
	} else {
		return p1.type == BEGGINING;
	}
}

void modifyCounter(CanCounter& counter, const Point& p) {
	int change = p.type == BEGGINING ? 1 : -1;
	switch (p.color)
	{
		case YELLOW:
			counter.yellow += change;
			break;

		case BLUE:
			counter.blue += change;
			break;
		
		case RED:
			counter.red += change;
			break;
	}
}

bool areGreenCans(const CanCounter& counter) {
	return counter.yellow >= 1 && counter.blue >= 1 && counter.red == 0;
}

ll numGreenCans(const vector<Point>& points) {
	CanCounter counter;
	ll numGreenCans = 0;

	int lastPos = 0;
	

	for(int i = 0; i < points.size();) {
		Point point = points[i];

		int j = i;
		while(points[j].pos == point.pos) {
			modifyCounter(counter, points[j]);
			j++;
		}
		i = j;

		if(areGreenCans(counter)) {
			numGreenCans += (point.pos - lastPos);
		}

		lastPos = point.pos;
	}

	return numGreenCans;
}

int main() {
	int numCans, numOperations;
	scanf("%i %i", &numCans, &numOperations);

	vector<Point> points = loadPoints(numOperations);
	sort(points.begin(), points.end());

	printf("%lli", numGreenCans(points));

	return 0;
}