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
#include <bits/stdc++.h>
using namespace std;
int n, m, kol, p, k;
const int POT=1048576;
bool tree[2*POT+10][3];

void wstaw(int kol, int p, int k, int w, int tp, int tk)
{
    if(tp>=p&&tk<=k){tree[w][kol]=true;return;}
    if(p<=(tp+tk)/2)wstaw(kol, p, k, w*2, tp, (tp+tk)/2);
    if(k>(tp+tk)/2)wstaw(kol, p, k, w*2+1, (tp+tk)/2+1, tk);
}

int sumuj(int w, int p, int k, bool zolty, bool niebieski)
{
    if(tree[w][2]||p>=n)return 0;
    if(p==k)return (tree[w][0]||zolty)&&(tree[w][1]||niebieski);
    return sumuj(w*2, p, (p+k)/2, zolty||tree[w][0], niebieski||tree[w][1])+sumuj(w*2+1, (p+k)/2+1, k, zolty||tree[w][0], niebieski||tree[w][1]);
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0; i<m; ++i)
    {
        cin>>p>>k>>kol;
        wstaw(kol-1, p-1, k-1, 1, 0, POT-1);
    }
    cout<<sumuj(1, 0, POT-1, false, false)<<"\n";
}