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
/*
 *  Copyright (C) 2020  Paweł Widera
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details:
 *  http://www.gnu.org/licenses/gpl.html
 */
#include <iostream>
#include <numeric>
#include <array>
#include <vector>
#include <algorithm>
using namespace std;


enum class EType { start, end };

struct Event {
	int x;
	int dye;
	EType type;

	int operator<(const Event& other) const {
		if (x == other.x) {
			return type < other.type;
		} else {
			return x < other.x;
		}
	}

	bool operator==(const Event& other) const {
		return x ==  other.x && dye == other.dye && type == other.type;
	}
};


bool is_green(array<int, 3>& c) {
	return c[0] > 0 && c[1] > 0 && c[2] == 0;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	int first, last, dye;
	vector<Event> events;

	cin >> n >> m;
	events.reserve(2 * m);

	for (int i = 0; i < m; ++i) {
		cin >> first >> last >> dye;
		--dye;
		events.push_back({first, dye, EType::start});
		events.push_back({last, dye, EType::end});
	}

	stable_sort(events.begin(), events.end());

	int count = 0;
	int previous = 1;
	bool prev_green = false;
	Event last_event = {0};
	array<int, 3> colour = {0};

	for (auto event: events) {
		bool new_state = event.x > last_event.x;
		bool update = ((new_state && event.type == EType::end)
			|| (!new_state && event.type == EType::end && last_event.type == EType::start));
		bool special_update = new_state && last_event.type == EType::start;

		// update count for the last (skipped) state
		if (special_update) {
			if (prev_green) {
				count += max(0, last_event.x - previous - 1);
			}
			if (is_green(colour)) {
				++count;
			}
			previous = last_event.x;
		}

		// remember if previous state (post removal) was green
		if (new_state) {
			prev_green = is_green(colour);
		}

		// update count for the current state
		if (update) {
			if (prev_green) {
				count += max(0, event.x - previous - 1);
			}
			if (is_green(colour)) {
				++count;
			}
			previous = event.x;
		}

		// mix in a new dye
		if (event.type == EType::start) {
			++colour[event.dye];
		}
		// remove a dye
		else {
			--colour[event.dye];
		}

		last_event = event;
	}

	cout  << count << endl;
	return 0;
}