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

using namespace std;

int main()
{
    cin.sync_with_stdio(0);
    vector<int> sorted; // numer puszki bity 3:31; open(0)/close(1) bit 2; kolor bity 0:1
    int n,m;
    cin >> n >> m;
    sorted.reserve(2*m);
    for(int i=0; i<m; ++i)
    {
        int l,r,k;
        cin >> l >> r >> k;
        sorted.push_back((l << 3) | k);
        sorted.push_back((r << 3) | 4 | k);
    }

    sort(sorted.begin(), sorted.end());

    int green = 0;
    int color_count[4] = {0,0,0,0};
    int puszka_start = 0;
    int puszka_stop = 0;
    while(1)
    {
        while(puszka_stop+1<sorted.size() && sorted[puszka_stop+1] >> 3 == sorted[puszka_start] >> 3)
        {
            puszka_stop++;
        }

        int i;
        for(i=puszka_start; i<=puszka_stop && !(sorted[i] & 4); ++i) // opening a range before current puszka
        {
            color_count[sorted[i] & 3]++;
        }

        if(color_count[1]>0 && color_count[2]>0 && color_count[3]==0)
            green++;

        for(; i<=puszka_stop; ++i) // closing a range after current puszka
        {
            color_count[sorted[i] & 3]--;
        }

        if(puszka_stop+1==sorted.size())
            break;
        puszka_start = puszka_stop + 1;
        puszka_stop = puszka_start;
        int prev_puszka = sorted[puszka_start-1] >> 3;
        int curr_puszka = sorted[puszka_start] >> 3;
        if(color_count[1]>0 && color_count[2]>0 && color_count[3]==0)
            green += curr_puszka-prev_puszka-1;
    }
    cout << green;

    return 0;
}