#include #include #include #include using int64 = std::int64_t; class SegmentTree { public: explicit SegmentTree(const std::vector& values) : n_(static_cast(values.size()) - 1), sum_(4 * n_ + 4), lazy_(4 * n_ + 4), has_lazy_(4 * n_ + 4, false) { minimum_.resize(4 * n_ + 4); maximum_.resize(4 * n_ + 4); build(1, 1, n_, values); } int64 range_sum(int left, int right) { if (left > right) return 0; return range_sum(1, 1, n_, left, right); } void range_assign(int left, int right, int64 value) { if (left <= right) range_assign(1, 1, n_, left, right, value); } int64 point_value(int position) { return range_sum(position, position); } // The maintained array is nondecreasing. Return n+1 if no value >= target. int first_at_least(int left, int64 target) { return first_at_least(1, 1, n_, left, target); } // Return 0 if no value <= target in [1, right]. int last_at_most(int right, int64 target) { return last_at_most(1, 1, n_, right, target); } private: int n_; std::vector sum_; std::vector minimum_; std::vector maximum_; std::vector lazy_; std::vector has_lazy_; void apply(int node, int left, int right, int64 value) { sum_[node] = value * (right - left + 1); minimum_[node] = maximum_[node] = value; lazy_[node] = value; has_lazy_[node] = true; } void push(int node, int left, int right) { if (!has_lazy_[node] || left == right) return; int middle = (left + right) / 2; apply(node * 2, left, middle, lazy_[node]); apply(node * 2 + 1, middle + 1, right, lazy_[node]); has_lazy_[node] = false; } void build(int node, int left, int right, const std::vector& values) { if (left == right) { sum_[node] = values[left]; minimum_[node] = maximum_[node] = values[left]; return; } int middle = (left + right) / 2; build(node * 2, left, middle, values); build(node * 2 + 1, middle + 1, right, values); sum_[node] = sum_[node * 2] + sum_[node * 2 + 1]; minimum_[node] = minimum_[node * 2]; maximum_[node] = maximum_[node * 2 + 1]; } int64 range_sum(int node, int left, int right, int query_left, int query_right) { if (query_left <= left && right <= query_right) return sum_[node]; push(node, left, right); int middle = (left + right) / 2; int64 result = 0; if (query_left <= middle) result += range_sum(node * 2, left, middle, query_left, query_right); if (query_right > middle) result += range_sum(node * 2 + 1, middle + 1, right, query_left, query_right); return result; } void range_assign(int node, int left, int right, int query_left, int query_right, int64 value) { if (query_left <= left && right <= query_right) { apply(node, left, right, value); return; } push(node, left, right); int middle = (left + right) / 2; if (query_left <= middle) range_assign(node * 2, left, middle, query_left, query_right, value); if (query_right > middle) range_assign(node * 2 + 1, middle + 1, right, query_left, query_right, value); sum_[node] = sum_[node * 2] + sum_[node * 2 + 1]; minimum_[node] = minimum_[node * 2]; maximum_[node] = maximum_[node * 2 + 1]; } int first_at_least(int node, int left, int right, int query_left, int64 target) { if (right < query_left || maximum_[node] < target) return n_ + 1; if (left == right) return sum_[node] >= target ? left : n_ + 1; push(node, left, right); int middle = (left + right) / 2; int result = first_at_least(node * 2, left, middle, query_left, target); if (result != n_ + 1) return result; return first_at_least(node * 2 + 1, middle + 1, right, query_left, target); } int last_at_most(int node, int left, int right, int query_right, int64 target) { if (left > query_right || minimum_[node] > target) return 0; if (left == right) return sum_[node] <= target ? left : 0; push(node, left, right); int middle = (left + right) / 2; int result = last_at_most(node * 2 + 1, middle + 1, right, query_right, target); if (result != 0) return result; return last_at_most(node * 2, left, middle, query_right, target); } }; struct Box { int index; int64 deadline; int64 target_normalized; }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int test_point, test_cases; std::cin >> test_point >> test_cases; (void)test_point; while (test_cases--) { int n; std::cin >> n; std::vector normalized(n + 1); std::vector boxes(n); for (int i = 1; i <= n; ++i) { int64 initial, target, deadline; std::cin >> initial >> target >> deadline; normalized[i] = initial - i; boxes[i - 1] = {i, deadline, target - i}; } std::sort(boxes.begin(), boxes.end(), [](const Box& lhs, const Box& rhs) { if (lhs.deadline != rhs.deadline) return lhs.deadline < rhs.deadline; return lhs.index < rhs.index; }); SegmentTree tree(normalized); int64 elapsed = 0; bool possible = true; for (const Box& box : boxes) { int i = box.index; int64 current = tree.point_value(i); int64 target = box.target_normalized; if (current < target) { int first = tree.first_at_least(i, target); int right = first - 1; int64 old_sum = tree.range_sum(i, right); elapsed += target * (right - i + 1) - old_sum; tree.range_assign(i, right, target); } else if (current > target) { int last = tree.last_at_most(i, target); int left = last + 1; int64 old_sum = tree.range_sum(left, i); elapsed += old_sum - target * (i - left + 1); tree.range_assign(left, i, target); } if (elapsed > box.deadline) possible = false; } std::cout << (possible ? "Yes\n" : "No\n"); } return 0; }