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

using namespace std;

int main()
{
    long n; // Liczba puszek
    long m; // Liczba operacji

    cin >> n >> m;

    map<long, short> puszki;
    map<long, short>::iterator pozycja, pozycja_nast;
    puszki.insert(make_pair(1, 0));

    while (m-- > 0) {
        long start, koniec, koniec_okresu;
        short kolor;
        cin >> start >> koniec >> kolor;
        if (kolor == 3) kolor = 4;

        //cout << "---" << start << " " << koniec << " " << kolor << endl;

        while (start <= koniec) {
            pozycja = puszki.lower_bound(start);
            if (pozycja == puszki.end() || pozycja->first > start)
                pozycja = prev(pozycja);
            short old_kolor = pozycja->second;
            short new_kolor = kolor | old_kolor;
            pozycja_nast = next(pozycja);
            koniec_okresu = n + 1;
            if (pozycja_nast != puszki.end())
                koniec_okresu = pozycja_nast->first;

            if (old_kolor != new_kolor) {
                if (pozycja->first < start) {
                    puszki.insert(make_pair(start, kolor | old_kolor));
                }
                else {
                    pozycja->second = kolor | old_kolor;
                }
                if (koniec < koniec_okresu - 1)
                    puszki.insert(make_pair(koniec + 1, old_kolor));
            }
            start = koniec_okresu;
        }
        // print content:
        //for (map<long, short>::iterator it = puszki.begin(); it != puszki.end(); ++it)
        //    cout << it->first << " => " << it->second << endl;
    }
    long ile = 0, popr = 1;
    short kolor = 0;
    for (map<long, short>::iterator it = puszki.begin(); it != puszki.end(); ++it) {
        if (it->first > 1 && kolor == 3)
            ile += (it->first - popr);
        popr = it->first;
        kolor = it->second;
    }
    if (kolor == 3)
        ile += (n + 1 - popr);
    cout << ile << endl;
    return 0;
}