gistfile1.cpp

#include<cstdio>
#include<vector>
#include<algorithm>
#define INF 2000000000
using namespace std;

struct event {
  int type; // 0 - start, 1 - end
  int x;
  int id;

  event(int _type, int _x, int _id) {
    type = _type; x = _x; id = _id;
  }
} /* optional variable list */;

struct story {
  int capacity;
  int used;

  story(int _capacity) {
    capacity = _capacity; used = 0;
  }
} /* optional variable list */;

int Z, n, tmp_start, tmp_end, tmp_capacity, counter;
vector< story > stories;
vector< event > events;

void precleaning();
void load_data();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
  scanf("%d", &Z);
  while(Z--) {
    precleaning();
    load_data();
    calculate();
    print_data();
  }
  return 0;
}

void precleaning() {
  events.clear(); stories.clear(); counter = 0;
}

void load_data() {
  scanf("%d", &n);

  for (int i = 0; i < n; i++) {
    scanf("%d %d %d", &tmp_start, &tmp_end, &tmp_capacity);
    stories.push_back(story(tmp_capacity));
    events.push_back(event(0, tmp_start, i));
    events.push_back(event(1, tmp_end, i));
  }
}

bool operator<(const event& a, const event& b) {
    if (a.x == b.x) return a.type < b.type;
    else return a.x < b.x;
}

void calculate() {
  sort(events.begin(), events.end());

  for (int i = 0; i < 2*n; i++) {
    story s = stories[events[i].id];
    if (events[i].type == 0) {
      stories[events[i].id].used = counter;
    } else {
      int tmp = s.capacity-(counter-s.used); 
      counter += (tmp > 0) ? tmp : 0;
    }
  }
}

void print_data() {
  printf("%d\n", counter);
}