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
#include <iostream>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

#ifdef HOME__
    #define PRINT(x) cerr<<x
#else
    #define PRINT(x)
#endif

#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x,n) for(__typeof(n.begin()) x = (n).begin(); x != (n).end(); ++x)
#define MUST1 1
#define MUST2 2
#define CANT  3

#define MAX_M 1000001

int n,m;
int l,r,k;
//std::multimap<int,int> events;
typedef pair<int,int> PII;
PII events[MAX_M*2];

bool compare(const PII& a, const PII& b) {
	return a.first < b.first;
}

int must1 = 0, must2 = 0, cant = 0;

int main() {
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    int doubleM = (m<<1);
    REP(x,m) {
        cin>>l>>r>>k;
        events[x<<1] = (make_pair(l, k));
        events[(x<<1)+1] = (make_pair(r+1, -k));
    }
    std::sort(events, events+doubleM, compare);
    int last = 0;
    int sum = 0;
    REP(x, doubleM) {
				const auto& elem = events[x];
        switch(elem.second) {
            case  MUST1: ++must1; break;
            case -MUST1: --must1; break;
            case  MUST2: ++must2; break;
            case -MUST2: --must2; break;
            case  CANT: ++cant; break;
            case -CANT: --cant; break;
        }
        PRINT(elem.first << " " << elem.second << " --> " << must1 << " " << must2 << " " << cant << endl);
        if (last != 0 && last != elem.first) {
            PRINT("Desired color in range " << last << " " << elem.first-1 << endl);
            sum += (elem.first - last); // (elem.first-1) - last + 1
        }
        if (must1 > 0 && must2 > 0 && cant == 0)
            last = elem.first;
        else
            last = 0;
    }
    cout << sum;
    return 0;
}