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
#include <bits/stdc++.h>

using namespace std;

bool cmp (pair<int, int> i, pair<int, int> j)
{
    if (i.first == j.first) return i.first < j.first;
    return i.second < j.second;
}

int main() {

  int n,m,ff,ll,cc;
  int green=0;

  pair <int, int> y,b,g;

  std::vector<pair<int, int>> yl;
  std::vector<pair<int, int>> bl;
  std::vector<pair<int, int>> rd;
  std::vector<pair<int, int>> gr;

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

  while (m--) {
    scanf("%i %i %i", &ff, &ll, &cc);
    if (cc==1) yl.push_back(make_pair(ff,ll));
    else if (cc==2) bl.push_back(make_pair(ff,ll));
    else rd.push_back(make_pair(ff,ll));
  }

  sort(yl.begin(), yl.end(), cmp);
  sort(bl.begin(), bl.end(), cmp);
  sort(rd.begin(), rd.end(), cmp);

  
  if (bl.empty() || yl.empty()) printf("0\n");

  int j=0;
  int i=0;
  b = bl[0];
  y = yl[0];
  while(i!=yl.size()&&j!=bl.size())
  {
    while (y.second < b.first)
    {
    i++;
    if (i==yl.size()) break;
    if (yl[i].first > y.second) y = yl[i];
    else y.second = yl[i].second;
    }

    while (b.second < y.first)
    {
      j++;
      if (j==bl.size()) break;
      if (bl[j].first > b.second) b = bl[j];
      else b.second = bl[j].second;
    }
    
    if (b.first <= y.second && y.first <= b.second)
    {
      green = green + 1 + min(b.second,y.second) - max(b.first,y.first);
      g.first = max(b.first,y.first);
      g.second= min(b.second,y.second);
      gr.push_back(g);

      b.first = 1 + min(b.second,y.second);
      y.first = 1 + min(b.second,y.second);
    }
  }



  //for (auto& it : gr)
  //cout<<it.first<<" "<<it.second<<endl;
  //printf("%i\n",green);

  #define bl gr
  #define yl rd
  j=0;
  i=0;
  b = bl[0];
  y = yl[0];
  while(i!=yl.size()&&j!=bl.size())
  {
    while (y.second < b.first)
    {
    i++;
    if (i==yl.size()) break;
    if (yl[i].first > y.second) y = yl[i];
    else y.second = yl[i].second;
    }

    while (b.second < y.first)
    {
      j++;
      if (j==bl.size()) break;
      if (bl[j].first > b.second) b = bl[j];
      else b.second = bl[j].second;
    }
    
    if (b.first <= y.second && y.first <= b.second)
    {
      green = green - 1 - min(b.second,y.second) + max(b.first,y.first);

      b.first = 1 + min(b.second,y.second);
      y.first = 1 + min(b.second,y.second);
    }
  }

  printf("%i\n",green);

  return 0;
}