Implementation approach

Suppose that we have processed entrance of up to group \((i-1)\), which occurred at time \(T_{i-1}\).

The time at which group \(i\) comes to the front of the queue can be found as \(\max(T_{i-1}, A_i)\).

At this point, if \(K\) people remain in the restaurant, then that time is exactly when group \(i\) enters the restaurant. Otherwise, we repeatedly remove a group that will leave earliest until there are \(K\) or less customers left. The time of group \(i\)’s entrance is the larger of \(A'_i\) and the latest time a group leaves.

To retrieve a group that will leave earliest, we can use a data structure called a priority queue. In languages like C++, this feature is provided as a standard feature, so we recommend to use this.

To keep track of the number of customers remaining in the restaurant, we can update by delta: whenever a group enters, increase the count by the number of people in the group; whenever a group leaves, reduce the count by the number.

Sample code (C++)

#include <iostream>
using std::cin;
using std::cout;
#include <vector>
using std::vector;
using std::pair;
#include <queue>
using std::priority_queue;
using std::greater;
using std::max;

typedef long long int ll;
typedef pair<ll, ll> P;


ll n, k;
vector<ll> a, b, c;

void solve () {
	priority_queue<P, vector<P>, greater<P> > que;

	vector<ll> ans(n, -1);
	ll sum = 0;
	ll t = 0;
	for (ll i = 0; i < n; i++) {
		t = max(t, a[i]);
		while (sum + c[i] > k) {
			P q = que.top(); que.pop();
			t = max(t, q.first);
			sum -= q.second;
		}

		ans[i] = t;
		que.push({t + b[i], c[i]});
		sum += c[i];
	}

	for (ll i = 0; i < n; i++) {
		cout << ans[i] << "\n";
	}
}

int main (void) {
	cin >> n >> k;
	a.resize(n);
	b.resize(n);
	c.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}

	solve();
	
	return 0;
}