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
#include<cstdio>
#include<algorithm>

using namespace std;

struct pol{
    int l;
    int r;
    int k;

    bool operator<(pol a)const{
        return l < a.l;
    }
};

static pol tab[1000000];

int main(){
    int n, m;

    scanf("%i%i", &n, &m);

    for(int i = 0; i < m; ++i){
        scanf("%i%i%i", &(tab[i].l), &(tab[i].r), &(tab[i].k));
    }

    sort(tab, tab + m);

    int pok[3];
    pok[0] = 0; pok[1] = 0; pok[2] = 0;

    int pop = 0;
    int sum = 0;

    for(int i = 0; i < m; ++i){
        int l = tab[i].l;
        if(l > pop){
            int skok = l - pop;

            int ziel = min(pok[0], pok[1]);
            ziel = min(ziel, skok);

            int czerw = min(skok, pok[2]);

            if(ziel > czerw){
                sum += ziel - czerw;
            }

            if(pok[0] > skok){
                pok[0] -= skok;
            }
            else{
                pok[0] = 0;
            }

            if(pok[1] > skok){
                pok[1] -= skok;
            }
            else{
                pok[1] = 0;
            }

            if(pok[2] > skok){
                pok[2] -= skok;
            }
            else{
                pok[2] = 0;
            }

            pop = l;
        }
        int k = tab[i].k - 1;
        int r = tab[i].r;

        int rozn = r - l + 1;
        if(pok[k] < rozn){
            pok[k] = rozn;
        }
    }

    int ziel = min(pok[0], pok[1]);

    int czerw = pok[2];

    if(ziel > czerw){
        sum += ziel - czerw;
    }

    printf("%i\n", sum);

    return 0;
}