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
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct cansNode {
  int canMin, canMax;
  bool yellow = false, blue = false, red = false;
  vector<cansNode*> childrens;
};

cansNode *newNode(int canMin, int canMax, int canColor = 0, cansNode *can = new cansNode) {
  cansNode *temp = new cansNode;
  temp->canMin = canMin;
  temp->canMax = canMax;
  temp->yellow = can->yellow || canColor == 1;
  temp->blue = can->blue || canColor == 2;
  temp->red = can->red || canColor == 3;
  return temp;
}

void debug(cansNode *cans, int lvl = 0) {
  printf("\n");
  if (lvl > 0) {
    string s = "";
    cout << s.append(lvl, ' ');
    printf("-> ");
  }
  printf("%d %d", cans->canMin, cans->canMax);
  if (cans->yellow) printf("-y-");
  if (cans->blue) printf("-b-");
  if (cans->red) printf("-r-");

  for(vector<cansNode*>::iterator it = cans->childrens.begin(); it != cans->childrens.end(); ++it) {
    debug(*it, lvl + 1);
  }
}

int count(cansNode *cans, bool isSub = false) {
  int cansNum = cans->canMax - cans->canMin + 1;
  int result = 0;

  if (cans->red) return isSub ? -cansNum : 0;

  if (!isSub && cans->yellow && cans->blue) {
    result = cans->canMax - cans->canMin + 1;
    isSub = true;
  }

  for(vector<cansNode*>::iterator it = cans->childrens.begin(); it != cans->childrens.end(); ++it) {
    result += count(*it, isSub);
  }
  return result;
}

void insert(cansNode *cans, int canMin, int canMax, int canColor) {
  if (cans->red) {
    return;
  }
  if (cans->canMin == canMin && cans->canMax == canMax) {
    cans->yellow = cans->yellow || canColor == 1;
    cans->blue = cans->blue || canColor == 2;
    cans->red = cans->red || canColor == 3;
    return;
  }
  // printf("INS %d, %d, %d\n", canMin, canMax, canColor);
  if (cans->childrens.size() == 0 && cans->canMin <= canMin && cans->canMax >= canMax) {
    cans->childrens.push_back(newNode(canMin, canMax, canColor, cans));
  } else if (cans->childrens.size() > 0) {
    if (cans->childrens.front()->canMin > canMax) {
      cans->childrens.insert(cans->childrens.begin(), newNode(canMin, canMax, canColor, cans));
    } else if (cans->childrens.back()->canMax < canMin) {
      cans->childrens.push_back(newNode(canMin, canMax, canColor, cans));
    } else {
      // printf("ent %d, %d, %d\n", canMin, canMax, canColor);
      for(int i = 0; i < cans->childrens.size(); ++i) {
        cansNode *child = cans->childrens[i];
        // printf("chd %d, %d\n", child->canMin, child->canMax);
        if (canMax > 0 && canMin >= child->canMin && canMax <= child->canMax) {
          // printf("ins %d, %d, %d\n", canMin, canMax, canColor);
          insert(child, canMin, canMax, canColor);
          canMax = 0;
        } else if (canMax > 0 && canMin < child->canMin) {
          // printf("min %d, %d, %d\n", canMin, child->canMin - 1, (int)cans->childrens.size());
          cans->childrens.insert(cans->childrens.begin() + i, newNode(canMin, child->canMin - 1, canColor, cans));
          canMin = child->canMin;
        } else if (canMin >= child->canMin && canMax >= child->canMax && canMin <= child->canMax) {
          // printf("max %d, %d, %d\n", canMin, child->canMax, canColor);
          insert(child, canMin, child->canMax, canColor);
          canMin = child->canMax + 1;
        }
      }
      if (canMin <= canMax) {
        // printf("maX %d, %d, %d\n", canMin, canMax, canColor);
        cans->childrens.push_back(newNode(canMin, canMax, canColor, cans));
      }
    }
  }
}

int main(int argc, char const *argv[]) {
  int cansNum, opsNum, canMin, canMax, canColor, result = 0, i, j;
  if (!scanf("%d %d", &cansNum, &opsNum)) return 1;

  cansNode *cans = newNode(1, cansNum);

  for (i = 0; i < opsNum; ++i) {
    if (!scanf("%d %d %d", &canMin, &canMax, &canColor)) return 1;
    // printf("\ninc %d, %d, %d\n", canMin, canMax, canColor);
    insert(cans, canMin, canMax, canColor);
  }

  // debug(cans);
  printf("%d", count(cans));

  return 0;
}