from queue import Queue
if __name__ == '__main__':
n, b = list(map(int, input().split()))
q = Queue()
next_avail = 0
task_list = []
for i in range(n):
t, d = list(map(int, input().split()))
task = [t, d, 0]
task_list.append(task)
start = 0
t0, d0, f0 = task_list[0]
next_avail = t0 + d0
task_list[0][2] = next_avail
q.put(next_avail)
for i in range(1, n):
temp_task = task_list[i]
while (q.qsize() > 0) and (temp_task[0] >= q.queue[0]):
q.get()
if next_avail <= temp_task[0]:
next_avail = temp_task[0] + temp_task[1]
temp_task[2] = next_avail
q.put(next_avail)
else:
if q.qsize() > b:
temp_task[2] = -1
else:
next_avail += temp_task[1]
temp_task[2] = next_avail
q.put(next_avail)
for t in task_list:
print(t[2], end=" ")#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int n, b;
cin >> n >> b;
b++;
vector<int> t(n);
vector<int> d(n);
vector<long long> ans(n);
for (int i = 0; i < n; i++) {
cin >> t[i] >> d[i];
}
queue<int> q;
q.push(0);
long long l = t[0];
long long r = t[0] + d[0];
int sz = 1;
for (int i = 1; i < n; i++) {
while (!q.empty() && l + d[q.front()] <= t[i]) {
int c = q.front();
q.pop();
l += d[c];
ans[c] = l;
sz--;
}
if (r > t[i]) {
if (sz < b) {
q.push(i);
sz++;
r += d[i];
}
else {
ans[i] = -1;
}
}
else if (r <= t[i]) {
while (!q.empty()) {
int c = q.front();
q.pop();
l += d[c];
ans[c] = l;
}
sz = 1;
q.push(i);
l = t[i];
r = t[i] + d[i];
}
}
while (!q.empty()) {
int c = q.front();
q.pop();
l += d[c];
ans[c] = l;
}
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
}/*1690754475.6171336*/528. Random Pick with Weight | 470. Implement Rand10() Using Rand7() |
866. Prime Palindrome | 1516A - Tit for Tat |
622. Design Circular Queue | 814. Binary Tree Pruning |
791. Custom Sort String | 787. Cheapest Flights Within K Stops |
779. K-th Symbol in Grammar | 701. Insert into a Binary Search Tree |
429. N-ary Tree Level Order Traversal | 739. Daily Temperatures |
647. Palindromic Substrings | 583. Delete Operation for Two Strings |
518. Coin Change 2 | 516. Longest Palindromic Subsequence |
468. Validate IP Address | 450. Delete Node in a BST |
445. Add Two Numbers II | 442. Find All Duplicates in an Array |
437. Path Sum III | 436. Find Right Interval |
435. Non-overlapping Intervals | 406. Queue Reconstruction by Height |
380. Insert Delete GetRandom O(1) | 332. Reconstruct Itinerary |
368. Largest Divisible Subset | 377. Combination Sum IV |
322. Coin Change | 307. Range Sum Query - Mutable |