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

struct Range : public std::map<int, int>
{
    void add(int l, int r);
    void diff(Range & r);
};

void Range::add(int l, int r)
{
    Range::iterator i, j;

    if (r < l)
        return;

    j = i = lower_bound(l);

    while (i != end() && i->first <= r) {
        r = i->second;
        ++i;
    }

    while (j != begin()) {
        --j;

        if (j->second < l) {
            ++j;
            break;
        }

        l = j->first;
    }

    erase(j, i);
    (*this)[l] = r;
}

Range cross(Range & a, Range & b)
{
    Range o;
    Range::iterator i, j;

    i = a.begin();
    j = b.begin();

    while (i != a.end() && j != b.end()) {
        if (i->second < j->first)
            ++i;
        else if (j->second < i->first)
            ++j;
        else if (i->second < j->second) {
            o.add(std::max(i->first, j->first), i->second);
            ++i;
        }
        else {
            o.add(std::max(i->first, j->first), j->second);
            ++j;
        }
    }

    return o;
}

void Range::diff(Range & r)
{
    Range::iterator i, j, k;

    i = begin();
    j = r.begin();

    while (i != end() && j != r.end()) {
        if (i->second < j->first)
            ++i;
        else if (j->second < i->first)
            ++j;
        else if (i->first < j->first) {
            int t = i->second;
            i->second = j->first - 1;
            add(j->second + 1, t);
        }
        else if (i->second <= j->second) {
            k = i;
            ++i;
            erase(k);
        }
        else {
            int a = j->second + 1;
            int b = i->second;
            k = i;
            ++i;
            erase(k);
            add(a, b);
        }
    }
}

int main(void)
{
    Range R[3];
    int n, m, i;

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

    for (i = 0; i < m; i++) {
        int l, r, k;

        scanf("%d%d%d", &l, &r, &k);
        R[k-1].add(l, r);
    }

    Range r1 = cross(R[0], R[1]);

    r1.diff(R[2]);

    n = 0;

    for (Range::iterator j = r1.begin(); j != r1.end(); ++j)
        n += j->second - j->first + 1;

    printf("%d\n", n);

    return 0;
}