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
#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#include <algorithm>

struct Interval
{
    unsigned start;
    unsigned end;
};

std::vector<Interval> mergeIntervals(std::vector<Interval> &arr1);
std::vector<Interval> getIntervalsIntersections(std::vector<Interval> &arr1, std::vector<Interval> &arr2);
bool compareInterval(Interval i1, Interval i2);

int main()
{
    std::ios_base::sync_with_stdio(0);
    unsigned n, m;
    std::cin >> n >> m;
    std::vector<Interval> color_intervals[3];
    for (unsigned i = 0; i < m; i++)
    {
        unsigned l, r, k;
        std::cin >> l >> r >> k;
        color_intervals[k - 1].push_back({l, r});
    }
    std::vector<Interval> yellow_merged_intervals = mergeIntervals(color_intervals[0]); // [2, 8]
    std::vector<Interval> blue_merged_intervals = mergeIntervals(color_intervals[1]); // [1, 2], [4,6]
    std::vector<Interval> red_merged_intervals = mergeIntervals(color_intervals[2]); // [6, 7]
    //std::vector<Interval> yellow_blue_intervals;
    //yellow_blue_intervals.insert(yellow_blue_intervals.end(), yellow_merged_intervals.begin(), yellow_merged_intervals.end());
    //yellow_blue_intervals.insert(yellow_blue_intervals.end(), blue_merged_intervals.begin(), blue_merged_intervals.end());
    std::vector<Interval> yellow_blue_intersection_intervals = getIntervalsIntersections(yellow_merged_intervals, blue_merged_intervals); //[2, 2], [4, 6]
    //std::vector<Interval> yellow_blue_red_intervals = yellow_blue_intersection_intervals;
    //yellow_blue_red_intervals.insert(yellow_blue_red_intervals.end(), red_merged_intervals.begin(), red_merged_intervals.end());
    std::vector<Interval> yellow_blue_red_intersection_intervals = getIntervalsIntersections(yellow_blue_intersection_intervals, red_merged_intervals);
    unsigned res = 0;
    for (Interval interval : yellow_blue_intersection_intervals)
        res += interval.end - interval.start + 1;
    for (Interval interval : yellow_blue_red_intersection_intervals)
        res -= interval.end - interval.start + 1;
    std::cout << res;
    /*std::vector<Interval> dupa = {{5, 5}, {1, 3}, {2, 5}, {7, 9}};
    std::vector<Interval> dupa1 = {{4, 9}, {2 , 3}, {11, 15}};
    std::vector<Interval> dupa2 = mergeIntervals(dupa); // [1, 5], [7, 9]
    std::vector<Interval> dupa3 = mergeIntervals(dupa1); // [2, 9], [10, 15]
    std::vector<Interval> dupa4 = dupa2;
    dupa4.insert(dupa4.end(), dupa3.begin(), dupa3.end());
    std::vector<Interval> dupa5 = getIntervalsIntersections(dupa4); // [2, 5], [7, 9]
    std::cout << dupa5[0].start << " " << dupa5[0].end << std::endl << dupa5[1].start << " " << dupa5[1].end;*/

    return 0;
}
bool compareInterval(Interval i1, Interval i2)
{
    return (i1.start < i2.start);
}

std::vector<Interval> mergeIntervals(std::vector<Interval> &arr)
{
    if (arr.size() <= 0)
        return arr;
    std::stack<Interval> s;
    std::sort(arr.begin(), arr.end(), compareInterval);
    s.push(arr[0]);
    for (unsigned i = 1; i < arr.size(); i++)
    {
        Interval top = s.top();
        if (top.end + 1 < arr[i].start)
        {
            s.push(arr[i]);
        }
        else if (top.end + 1 <= arr[i].end)
        {
            s.pop();
            top.end = arr[i].end;
            s.push(top);
        }
    }
    std::vector<Interval> res;
    while(!s.empty())
    {
        res.push_back(s.top());
        s.pop();
    }
    return res;
}
/*std::vector<Interval> getCommonIntervalsPart(std::vector<Interval> &arr1, std::vector<Interval> &arr2)
{
    if (n <= 0)
        return;
    std::sort(arr1.begin(), arr1.end(), compareInterval);
    std::sort(arr2.begin(), arr2.end(), compareInterval);
    std::stack<Interval> s1;
    std::stack<Interval> s2;
    int counter = 0;
    for (int i = 0 ; i < arr.size(); i++)
    {

        Interval top = s1.top();
        if (top.end < arr[i].start)
            s.push(arr[i]);
        else if (top.end < arr[i].end)
        {
            top.end = arr[i].end;
            s.pop();
            s.push(top);
        }
    }
}*/
std::vector<Interval> getIntervalsIntersections(std::vector<Interval> &arr1, std::vector<Interval> &arr2)
{
    std::vector<Interval> res;
    if (arr1.size() <= 0 || arr2.size() <= 0)
        return res;
    std::sort(arr1.begin(), arr1.end(), compareInterval);
    std::sort(arr2.begin(), arr2.end(), compareInterval);
    unsigned i = 0;
    unsigned j = 0;
    while (i < arr1.size() && j < arr2.size())
    {
        unsigned start = std::max(arr1[i].start, arr2[j].start);
        unsigned end = std::min(arr1[i].end, arr2[j].end);
        if  (end >= start)
            res.push_back({start, end});
        if (arr1[i].end > arr2[j].end)
            j++;
        else
            i++;
    }
    return res;
}