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
#include<vector>
#include<cstdio>
#include<utility>
#include<algorithm>
/*author: Michal Wodka
 */
using namespace std;

bool compareInterval(pair<int,int> i1, pair<int,int> i2)
{
    if (i1.first < i2.first){
	    return true;
    }
    if (i1.first > i2.first){
            return false;
    }
    
    return (i1.second < i2.second);
}

int main(){
        int m,n;
	scanf("%d%d", &n,&m);
	vector<pair<int,int>> zolty, zielony, niebieski, czerwony;
	zolty = zielony = niebieski = czerwony = vector<std::pair<int,int>>();
	for (int i=0; i<m; i++){
                int l,r,k;
		scanf("%d%d%d", &l, &r, &k);
		if (k == 1)
		    zolty.push_back(make_pair(l,r));
                if (k==2)
		    niebieski.push_back(make_pair(l,r));
	        if (k == 3)
		    czerwony.push_back(make_pair(l,r));
        }		
	sort(zolty.begin(), zolty.end(), compareInterval);
        sort(niebieski.begin(), niebieski.end(), compareInterval);
        sort(czerwony.begin(), czerwony.end(), compareInterval);


	//tworzymy zielony
	auto itZ = zolty.begin();
	auto itN = niebieski.begin();
	if (itN == zolty.end() || itZ == zolty.end()){
		printf("0\n");
		return 0;
        }
	int lz = itZ->first;
	int rz;
	int ln = itN->first;
	int rn;
	int result = 0;
	while( itZ != zolty.end() && itN != niebieski.end()){
	    ln = max(ln, itN->first);
            rn = itN->second;
	    lz = max(lz, itZ->first);
	    rz = itZ->second;
	    if (lz > rn || ln > rn){
		itN++;
		continue;
	    }
	    if (ln > rz || lz > rz){
		itZ++;
		continue;
	    }
             
	    int lzielony = max(lz,ln);
	    int rzielony = min(rz,rn);
	    zielony.push_back(make_pair(lzielony, rzielony));
	    result += rzielony - lzielony + 1;
            ln = lz = rzielony + 1;
	    if (ln > rn)
	        itN++;
	    if (lz > rz)
	        itZ++;
	}

	if (result == 0){
	    printf("0");
	    return 0;
	}

	auto itZiel = zielony.begin();
	auto itC = czerwony.begin();
	if (itC == czerwony.end()){
	    printf("%d\n", result);
	    return 0;
        }
	int rc;
	int lc = itC->first; 
        lz = itZiel->first;
        while (itZiel != zielony.end() && itC != czerwony.end()){
            lc = max(lc, itC->first);
            rc = itC->second;
            lz = max(lz, itZiel->first);
            rz = itZiel->second;
            if (lz > rc || lc > rc){
                itC++;
                continue;
            }
            if (lc > rz || lz > rz){
                itZiel++;
                continue;
            }
            int lbrazowy = max(lz,lc);
            int rbrazowy = min(rz,rc);
            result -= rbrazowy - lbrazowy + 1;
	    lc = lz = rbrazowy + 1;
            if (lc > rc)
                itC++;
            if (lz > rz)
                itZiel++;

	}
        printf("%d\n", result);	
	return 0;
}