A social network for dogs called DH (DogHouse) has k special servers to recompress…
- User
A social network for dogs called DH (DogHouse) has k special servers to recompress uploaded videos of cute cats. After each video is uploaded, it should be recompressed on one (any) of the servers, and only after that it can be saved in the social network.
We know that each server takes one second to recompress a one minute fragment. Thus, any server takes m seconds to recompress a m minute video.
We know the time when each of the n videos were uploaded to the network (in seconds starting from the moment all servers started working). All videos appear at different moments of time and they are recompressed in the order they appear. If some video appeared at time s, then its recompressing can start at that very moment, immediately. Some videos can await recompressing when all the servers are busy. In this case, as soon as a server is available, it immediately starts recompressing another video. The videos that await recompressing go in a queue. If by the moment the videos started being recompressed some servers are available, then any of them starts recompressing the video.
For each video find the moment it stops being recompressed. Input
The first line of the input contains integers n and k (1 ≤ n, k ≤ 5·105) — the number of videos and servers, respectively.
Next n lines contain the descriptions of the videos as pairs of integers si, mi (1 ≤ si, mi ≤ 109), where si is the time in seconds when the i-th video appeared and mi is its duration in minutes. It is guaranteed that all the si's are distinct and the videos are given in the chronological order of upload, that is in the order of increasing si.
Output
Print n numbers e1, e2, ..., en, where ei is the time in seconds after the servers start working, when the i-th video will be recompressed.
Examples
Input
3 2 1 5 2 5 3 5
Output
6 7 11
Input
6 1 1 1000000000 2 1000000000 3 1000000000 4 1000000000 5 1000000000 6 3
Output
1000000001 2000000001 3000000001 4000000001 5000000001 5000000004
Assistant
We need to solve a classic problem: given k servers (machines) that process jobs. Jobs arrive at times s_i (distinct, increasing). Each job has processing time p_i = m_i (in seconds? Actually m_i minutes but recompress time is m_i seconds per minute fragment, so total time = m_i seconds? Wait careful: "each server takes one second to recompress a one minute fragment. Thus, any server takes m seconds to recompress a m minute video." So processing time = m_i seconds. So p_i = m_i seconds. That's straightforward.
We have a queue. When a job arrives, if any server is free at that moment, it starts immediately. Otherwise it waits in queue. As soon as a server becomes free, it picks the next job from the queue (FIFO). Need to compute finish time for each job.
This is basically simulation of a multiserver FIFO queue (k servers). n up to 5e5, processing times and arrival times up to 1e9, need O(n log k) or similar.
Standard approach: maintain a priority queue of available times for each server (when they become free). Initially all servers free at time 0? Actually servers start working at time 0 (the time reference). So initially each server is free at time 0. But careful: If first job arrives at s1, it can start at max(s1, earliest free time). Since servers start at 0, earliest free time = 0. So start = s1 if any server free? But need to assign to a server that is free. So we can keep a min-heap of free times (the times when servers become idle). When a job arrives at time s, we check if any server is free at time s. That means the smallest free time <= s. Actually if the earliest free time <= s, then that server (and maybe others) is free. But we need to assign to one server. Since all servers are identical, we can just pop the smallest free time from the heap. That server will start the job at max(s, free_time). Then its new free time = start + p_i. Push back to heap.
But what if the smallest free time > s? That means no server is free at time s; all are busy. Then we need to wait until the earliest server finishes. In FIFO order, the next job to start is the one at head of queue? But we are processing jobs in order of arrival; we can simulate each job as it arrives. The typical method: Use a min-heap for server free times. For each job (in order of arrival), we check the heap: if the size of heap < k? Actually heap always contains k entries? We maintain a heap of free times for all k servers. Initially, all free at 0. For each job:
- Let s = arrival, p = processing.
- Let t = max(s, heap.min()) // this is when a server becomes available (the earliest free time). But careful: In FIFO, if a server becomes free before s, but there are no jobs waiting (queue empty), then when job arrives at s, it can start immediately. That corresponds to heap.min() <= s. So t = s if heap.min() <= s else heap.min() (the earliest free time). But is that correct for FIFO? Actually FIFO with multiple servers: when a job arrives, if there is any idle server, it starts immediately. The earliest idle server might have been idle since time 0 or earlier? But we have to pick any idle server. The start time = s. So if heap.min() <= s, we can pop that server (the one with smallest free time) and assign it start at s. That's okay because that server is free at or before s. However, there could be other servers with free time > s but still there might be servers free at s? Actually if the smallest free time <= s, then at least that server is free. So we can assign to it. The start time is s. That's fine. The new free time = s + p.
But what about case when smallest free time > s? Then all servers are busy at s. The job must wait. In a FIFO queue, the job that arrives next will be processed after all previously waiting jobs? But we are processing arrivals in order. The typical algorithm: When a job arrives, we need to assign it to the server that becomes free the earliest. However, that server might be busy until time free_time. Since we are simulating jobs in order of arrival, we can pop the smallest free time (the server that becomes free earliest) and set start = max(s, free_time) which in this case is free_time (since free_time > s). Then new free_time = free_time + p. This effectively puts the job onto that server as soon as it's free. But is that correct for FIFO? Let's think: Suppose we have jobs arriving at times s1, s2, ... and we have a queue. If at time s2, all servers are busy and there is already a queue? But when we process each job in order, we maintain the heap of server free times. If we immediately assign each arriving job to the earliest free server, we are essentially using a "any available server" but the order of service is determined by the order we pop servers. However, we need to ensure that when multiple jobs are waiting, the one that arrived earlier gets served first. In this approach, if we assign each job to a server at its arrival time (by popping the smallest free time), but if the server is not free until later, we effectively schedule it to start at that later time. However, could this cause a later-arriving job to be scheduled before an earlier-arriving job if the earlier job was scheduled to a server that becomes free later? Let's examine.
Suppose we have 2 servers. Jobs: J1: s=0, p=10 J2: s=1, p=1 J3: s=2, p=1
At time 0: heap [0,0]. Pop min (0), assign to J1 start=0, free becomes 10, push 10. Heap now [0,10]? Actually we popped one, so left one server with free time 0. Actually we need to maintain heap size = k. Initially all k free times = 0. When we process a job, we pop the smallest free time (that server). We compute start = max(s, free_time). Then push back free_time = start + p. That's correct.
Processing J1: pop 0, start = max(0,0)=0, free = 10, push 10. Heap now [0,10]? Wait we had two zeros initially. After popping one, we still have one zero left (the other server). So heap contains [0,10]. Yes.
J2 arrives at s=1: pop min=0 (since 0 <=1). This server is free at time 0, so start = max(1,0)=1. free=2, push 2. Heap now [2,10].
J3 arrives at s=2: pop min=2 (since 2 <=2? Actually 2 <=2, yes it's free at time 2). So start = max(2,2)=2, free=3, push 3. Heap now [3,10].
Finish times: J1:10, J2:2, J3:3. That matches FIFO? Let's think: At time 0, J1 starts on server A. Server B idle. At time 1, J2 arrives and immediately starts on server B (since idle). At time 2, J2 finishes? Actually J2 p=1, started at 1, finishes at 2. At time 2, server B becomes free. J3 arrives at time 2, so can start on server B at 2. That's correct. So order is fine.
Now consider a scenario where a job arrives while all servers busy and there is already a queue. For FIFO, the earliest arrived job in queue should get served next when any server becomes free. Our method of processing each job on arrival and assigning it to the earliest free server at that moment might not respect the queue order if multiple jobs are waiting? Actually, if we process jobs sequentially in order of arrival, we always assign a job at its arrival time to the earliest available server (or schedule it to start at that server's free time if none free). But is that equivalent to FIFO? Let's test.
Suppose k=1 (single server). Then heap initially [0]. For each job in order:
- J1: pop 0, start = max(s1,0), push start+p.
- J2: pop earliest free time (which is finish time of J1), start = max(s2, free_time), push new finish. That's exactly FIFO for single server.
Now for k>1, does the algorithm replicate FIFO? The standard solution for this problem (like "fast food" or "process tasks with multiple threads") uses a min-heap of finish times. Each task is processed in order: pop the earliest finish time, compute start = max(arrival, that time), then push new finish. This yields correct finish times for a FIFO queue with multiple servers? I recall problems like "Restaurant" or "Load Balancing" where tasks are assigned to the next available server. This is indeed the algorithm for scheduling tasks to identical machines in order of arrival, where tasks are queued and machines become free. The algorithm is: maintain a priority queue of times when each server becomes free. For each task in order:
- Let earliest = min heap top.
- If earliest <= arrival, then start = arrival (use that server), else start = earliest (wait).
- Then pop and push new finish = start + duration.
But is this equivalent to a FIFO queue? Consider the following scenario: k=2. Jobs: J1: s=0, p=5 J2: s=1, p=5 J3: s=2, p=5
Process:
- J1: pop 0, start=0, finish=5, push 5. Heap [0,5]? Actually one server remains free at 0.
- J2: pop 0 (since 0 <=1), start=1, finish=6, push 6. Heap now [5,6] (since the popped server had free time 0? Actually we popped the 0, the other server still has 0? Wait we had two zeros initially. After J1, we pushed 5 and still have one zero. So heap has [0,5]. For J2, we pop min=0, start=1, push 6. So heap becomes [5,6].
- J3: pop min=5 (since 5 <=2? No, 5 >2). So start=5, finish=10, push 10. Heap becomes [6,10]. Finish times: J1=5, J2=6, J3=10.
Now simulate manually: At time 0, J1 starts on server A. Server B idle. Time 1: J2 arrives, starts on server B (idle). So server B busy until 6. Time 2: J3 arrives, both servers busy (A busy until 5, B busy until 6). So J3 waits. At time 5, server A becomes free, so J3 starts on A at 5, finishes at 10. So correct.
Now test scenario where order might be violated: Suppose jobs arrive closely and one server becomes free earlier but there is a waiting job that arrived later? But FIFO ensures that the waiting queue is processed in order. Our algorithm processes each job in arrival order and assigns it to the earliest free server at that moment. When a job arrives and all servers are busy, we pop the earliest free time (which is the time the next server becomes free) and schedule the job to start at that time (which is essentially enqueuing it to that server). However, note that if multiple jobs are waiting, we need to ensure that when a server becomes free, it picks the job that arrived earliest among those waiting. In our algorithm, because we process jobs sequentially, we are effectively assigning each job to a server at arrival time, but that assignment may cause a later job to be scheduled to a server that becomes free earlier than the server assigned to an earlier job? Let's try to construct a counterexample.
Suppose k=2. Jobs: J1: s=0, p=10 J2: s=1, p=1 J3: s=2, p=10
Our algorithm:
- J1: pop 0, start=0, finish=10, push10. Heap[0,10]? Actually other server free at 0.
- J2: pop 0 (since 0<=1), start=1, finish=2, push2. Heap [2,10].
- J3: pop min=2 (since 2<=2? 2<=2 yes, but check: 2 <= s=2, so server free at time 2). So start= max(2,2)=2, finish=12, push12. Heap [10,12].
Finish: J1=10, J2=2, J3=12.
Manual simulation: time0 J1 on serverA (until10). ServerB idle. time1 J2 arrives, serverB idle, starts on B, finishes at2. time2 J2 finishes, serverB free. J3 arrives at time2, serverB free, so J3 starts on B at2, finishes12. That's correct.
Now consider jobs where one server becomes free very soon but a later job might get assigned to it earlier than an earlier job that is waiting? But in FIFO, the waiting queue forms only when all servers busy. If a server becomes free while there are waiting jobs, it takes the first from the queue. In our algorithm, we assign jobs at arrival to a server based on earliest free time. This can be seen as: when a job arrives, we look at the earliest time a server will be free. If that time is <= arrival, we assign it to that server starting at arrival. If it's > arrival, that means all servers are busy and there is at least one job waiting? Actually, if the earliest free time > arrival, then all servers are busy. But there might be other jobs that have been assigned earlier and are waiting? In our algorithm, earlier jobs have already been assigned to servers (by popping from heap and pushing their future finish times). So the heap contains the future finish times of all currently assigned jobs (including those that are waiting? Actually in our algorithm, when we assign a job, we set its start time as max(s, free_time). If free_time > s, that means we scheduled it to start at free_time, which is in the future. That job is effectively "waiting" for that server. The heap then holds the times when each server will become free, which includes jobs that may be scheduled to start later (i.e., waiting). So the heap represents the next available times for each server, considering all jobs that have been assigned to them so far. When a new job arrives, we pop the smallest free time (i.e., the server that will become free earliest). That server may currently be busy, but its free time is the earliest among all. If that free time is > s, then that server will be free later, and we assign the new job to start at that free_time. But what about the possibility that there is another server that becomes free later but there is a job that arrived earlier that is assigned to the earliest free server? Wait, we need to think of the ordering: In a FIFO queue, when a server becomes free, it takes the next job from the queue. This is equivalent to: maintain a queue of waiting jobs. When a job arrives, if a server is free, it starts immediately; else it enqueues. When a server finishes a job, it dequeues the next waiting job (if any) and starts it at that time. This is the natural discrete-event simulation. Our algorithm with heap and processing jobs in order of arrival is a known efficient way to compute finish times without simulating events for each completion. Why is it correct? Let's reason.
Consider we have a sequence of jobs. Let the servers be identical. The schedule is determined by the rule: at any time, if there is an idle server and a waiting job, the job starts immediately. This yields a deterministic schedule: it's like a multiserver FCFS queue. The finish times can be computed by iterating jobs and maintaining the earliest time any server becomes free. The algorithm is:
Initialize a min-heap of size k with zeros. For each job i (sorted by arrival time): let t = heap.pop() // earliest free time start_i = max(s_i, t) finish_i = start_i + p_i heap.push(finish_i)
This indeed gives correct finish times. I've seen this in many coding problems (e.g., "C. Queue" or "Bank" problem). The reasoning: At any point, the heap stores the times at which each server will become free. When a new job arrives, it will be handled by the server that becomes free the earliest among all servers. The job's start time is the later of its arrival and that server's free time. This matches the FIFO discipline because when a server becomes free, it picks the next job from the queue; since we are processing jobs in order of arrival, the next job to be served is exactly the one we are currently handling? But careful: Suppose we have jobs J1, J2, J3 arrive at times s1 < s2 < s3. Let's simulate the queue with an actual event-based approach: At time s1, if there's an idle server, J1 starts. Then at time s2, depending on server status, either starts immediately or enqueues. At time s3, similarly. When servers finish, they dequeue. The key is that the order in which jobs get assigned to servers is exactly the order of their arrival, because the queue is FIFO. That is, the first job to start among waiting jobs is always the one that arrived earliest among those not yet started. So if we process jobs in order of arrival and each time assign to the earliest finishing server, does that maintain the property that when a server becomes free, it will pick the next job in arrival order? I think yes because we are assigning jobs to servers in the order they'd be taken from the queue.
Consider a scenario: two servers, jobs J1 (s=0,p=10), J2 (s=2,p=3), J3 (s=4,p=3). Let's compute with algorithm:
- J1: pop0, start0, finish10, push10. Heap[0,10].
- J2: pop0 (free), start2, finish5, push5. Heap[5,10].
- J3: pop5 (since 5 >4? Actually 5 >4, so no free), start5, finish8, push8. Heap[8,10]. So finish: J1=10, J2=5, J3=8. Manual: time0 J1 on A. Server B idle. time2 J2 arrives, B free, starts on B, finishes at5. time4 J3 arrives, both servers busy (A until10, B until5). So J3 waits. At time5, B free, J3 starts, finishes at8. So correct.
Now consider a scenario where two jobs arrive while both servers busy, and the one that arrives later might have a shorter processing time? But order still FIFO: first arrived gets served first. Let's test: k=2, J1: s=0,p=10; J2: s=1,p=10; J3: s=2,p=1. According to FIFO: At time0, J1 starts on A. Server B idle. At time1, J2 arrives, B free, starts on B. Both busy until time10 and time11? Actually J2 start at1, finishes at11. So at time2, J3 arrives, both busy -> J3 waits. The next server to become free is A at time10. So J3 starts at10, finishes at11. So finish times: J1=10, J2=11, J3=11. Algorithm:
- J1: pop0, start0, finish10, push10. Heap[0,10].
- J2: pop0, start1, finish11, push11. Heap[10,11].
- J3: pop10 (min=10 >2? Actually 10 >2, so start=10), finish=11, push11. Heap[11,11]. Matches.
Now consider scenario where a job arrives after some jobs have been assigned but the earliest free time is from a server that has a job assigned that starts later? Actually the heap contains finish times for each server. Those finish times represent when the server will complete its currently assigned job(s). If we assign a new job to a server that currently has a job scheduled to finish later, the new job will start after that finish time. So the heap value is the server's next free time. So pop min gives the server that will be free earliest, which is exactly the server that would next become idle. In a FIFO queue, when a job arrives and all servers busy, it will wait until some server becomes free, and the first server to become free will take the next job. That matches: we assign the new job to the server that will be free earliest. But what if there is already a waiting job that arrived earlier and has been assigned to a server that becomes free later? In our algorithm, earlier jobs have already been assigned to some servers. When a later job arrives, we pop the earliest free time. That earliest free time might be from a server that currently has a job scheduled (maybe the earlier job). But if there is an earlier job that is waiting (i.e., assigned to a server but start time > arrival?), we need to ensure that the later job does not get scheduled before the earlier waiting job. But note that the earlier waiting job is already assigned to some server. Its start time is determined when it arrived: it was assigned to the server that was the earliest free at that time. That server's free time at that moment might be later than the current earliest free time? Let's examine if that could happen.
Suppose we have two servers. Job A arrives at time 0, p=100. Job B arrives at time 1, p=1. Job C arrives at time 2, p=1. Process with algorithm:
- A: pop0, start0, finish100, push100. Heap[0,100]? Actually other server free at0.
- B: pop0, start1 (since 0<=1), finish2, push2. Heap[2,100].
- C: pop2, start2 (since 2<=2), finish3, push3. Heap[3,100]. Seems fine.
But consider scenario: A arrives at time0, p=10; B arrives at time5, p=10; C arrives at time6, p=1. However, there might be a scenario where after assigning A and B, the earliest free time is from the server that got B, but B might have a later start? Let's compute: k=2.
- A: pop0, start0, finish10, push10. Heap[0,10].
- B: pop0 (since free), start5, finish15, push15. Heap[10,15].
- C: pop10 (since 10 >6? Actually 10 >6, so start=10), finish=11, push11. Heap[11,15]. So C assigned to server that had A (free at10). That's correct because after A finishes at10, server becomes free and should take next waiting job (which is C? But wait, what about B? B started at5 on other server, finishes at15. At time6 when C arrives, both servers busy: A until10, B until15. So queue: C. At time10, A's server free, picks C, finishes at11. So correct.
Now consider scenario where earlier job might have to wait longer because it was assigned to a server that becomes free later? But is it possible that when an earlier job arrives and all servers busy, it gets assigned to a server whose free time is not the earliest? In our algorithm, we always pop the minimum free time. So the earlier job always gets the earliest free server at that time. So it gets the best possible start. For later jobs, they might be assigned to servers that become free later, but that's because the earlier job already took the earliest server. So order is preserved.
Hence the algorithm is correct.
Now we need to implement it efficiently for up to 5e5 jobs. Use a min-heap (priority queue) of long long (since times can be up to 1e9 + sum of durations could be large, up to 5e5 * 1e9 = 5e14, so need 64-bit). In C++, use priority_queue with greater comparator (min-heap). Or we can use a multiset, but heap is fine.
Initialize heap with k zeros. For each job i: long long free_time = heap.top(); heap.pop(); long long start = max((long long)s_i, free_time); long long finish = start + m_i; ans[i] = finish; heap.push(finish);
That's it. Complexity O(n log k). Since k <= 5e5, log k ~ 19, fine.
One nuance: Are servers initially idle at time 0? The problem says: "We know the time when each of the n videos were uploaded to the network (in seconds starting from the moment all servers started working)." So at time 0, servers start working (they are ready). So yes, they are free at time 0.
Edge cases: n could be less than k. Then for first n jobs, they will get servers free immediately, start at s_i, finish = s_i + m_i.
Now let's test on given examples:
Example1: n=3,k=2 (1,5), (2,5), (3,5) Initialize heap [0,0] i1: pop0, start=max(1,0)=1, finish=6, push6. heap[0,6] i2: pop0, start=max(2,0)=2, finish=7, push7. heap[6,7] i3: pop6, start=max(3,6)=6, finish=11, push11. heap[7,11] Output: 6,7,11 matches.
Example2: n=6,k=1 All but last huge. i1: s=1, m=1e9 => pop0, start=1, finish=1e9+1, push. i2: pop1e9+1, start=max(2,1e9+1)=1e9+1, finish=2e9+1? Actually 1e9+1+1e9 = 2e9+1? Wait m_i=1e9 for first five. So finish1 = 1e9+1; i2: start= max(2, 1e9+1) = 1e9+1, finish = 1e9+1+1e9 = 2e9+1? That's 2,000,000,001? Actually 1e9 = 1000000000, so 1000000001 + 1000000000 = 2000000001, yes. Similarly i3: 3000000001, i4:4000000001, i5:5000000001. i6: s=6, m=3. At i6: pop top = 5000000001? Actually after i5, heap top is 5000000001. start=max(6,5000000001)=5000000001, finish=5000000004. So outputs: 1000000001,2000000001,3000000001,4000000001,5000000001,5000000004 matches.
So algorithm works.
Now we need to implement in C++ (or whatever). Input size up to 5e5, use fast I/O.
One caution: Using heap of size k could be large but k up to 5e5, fine.
We should use a min-heap: priority_queue<long long, vector, greater> pq; and initialize with k zeros. But if k is large, pushing k zeros might be O(k). That's okay (5e5). Alternatively we can start with empty heap and treat as if there are k servers available. When heap size < k, we can treat free_time = 0. But easier: initialize with k zeros.
But careful: If we push k zeros, then for each job we pop one, push one, heap size remains k. For n jobs, that's fine.
Edge case: n could be larger than k? That's typical. For n < k, we would have heap size k, but we only pop n times; we don't need to pop all. That's fine.
Thus solution is straightforward.
Now let's think about any subtlety: The times s_i are distinct and given in increasing order. So we don't need to sort.
We need to output each finish time on separate line.
Now for complexity, O(n log k). With n,k up to 5e5, log k ~ 19, so ~10 million operations, fine.
Thus final solution is just that.
But let's double-check the logic with more complex scenario: If the heap has multiple servers free (i.e., free_time <= s_i). When we pop the min, we might get a free_time that is not the smallest? Actually min is smallest, which could be <= s_i. If there are multiple free, the one we pick (the smallest) doesn't matter because all are free. So using min is fine.
Potential issue: The heap might have some free times that are less than s_i, but there could also be free times that are greater than s_i. But we always pop the smallest, which will be <= s_i if any free server exists. So that's correct.
Thus solution stands.
Now about data types: s_i and m_i up to 1e9, but finish times can be up to n * 1e9 or more? Actually worst-case: k=1, n=5e5, each s_i could be small but distinct. Actually s_i can be up to 1e9 but distinct; they might be increasing but not necessarily consecutive. However, worst-case finish time could be sum of m_i plus maybe large s_n. Since each m_i up to 1e9, sum up to 5e14. So 64-bit needed. Use long long.
Now implement.
Pseudo:
#include <bits/stdc++.h> using namespace std; typedef long long ll;
int main() { ios::sync_with_stdio(false); cin.tie(0);
int n, k; cin >> n >> k; priority_queue<ll, vector<ll>, greater<ll>> pq; for (int i = 0; i < k; ++i) pq.push(0LL); for (int i = 0; i < n; ++i) { ll s, m; cin >> s >> m; ll free = pq.top(); pq.pop(); ll start = max(s, free); ll finish = start + m; pq.push(finish); cout << finish << '\n'; } return 0;}
That's it.
But wait: Is there any nuance about the order of servers? Suppose we have k servers, and we pop the smallest free time. This is essentially always picking the server that becomes free earliest. However, is it possible that in a real FIFO system, when a job arrives and all servers are busy, the job goes to the queue; then when a server becomes free, it takes the first job from the queue. That server could be any that becomes free, not necessarily the earliest? Actually when a server becomes free, it immediately takes the next job. So the job that starts next is the one that has been waiting the longest, and it starts at the time that server becomes free. So the start time of a waiting job is exactly the time when some server becomes free. But which server? It could be any server that becomes free. In a FIFO queue, the order of service is determined solely by arrival order, not by which server is available first? Actually if multiple servers become free at the same time, they all take the next jobs from the queue (but there is still order). However, if servers become free at different times, the first server to become free will take the next waiting job. That is, the earliest free time among servers is the time when the next waiting job starts. Because if there is a waiting job, as soon as any server becomes free, it will start that job. The earliest free server determines the start time of the next waiting job. Therefore, for each arriving job, when it becomes the head of the queue, its start time will be the minimum among the free times of servers at that moment (which could be later than arrival). So our algorithm which assigns each arriving job to the server with earliest free time at that moment effectively simulates that the job will be started at the earliest possible moment given the current state (which includes future commitments). But wait: Is it always true that the job we are processing now (the i-th in order) will be the one that starts at the earliest free time? Yes, because when we process the i-th job, all previous jobs have already been assigned and are either already started or will start at some future times. The queue at that point consists of jobs that have arrived but not yet assigned to a server? In our algorithm, we assign immediately upon arrival, which might not match the concept of a queue: in a queue, if a job arrives and no server is free, it waits, but we don't decide which server it will go to until a server becomes free. However, our immediate assignment to a specific server (the one that will be free earliest) is equivalent to deciding at arrival which server will eventually process it, but that decision could be different from what happens in a dynamic system where servers pick jobs upon completion? In a FIFO system with multiple identical servers, the assignment of jobs to specific servers is not predetermined; but the start times are deterministic. Actually, the assignment to specific servers might not be unique, but the start times are determined. Our algorithm yields a particular assignment, but importantly it yields correct start (and thus finish) times. This is a known approach.
We can also think of it as: we maintain the times at which each server will be free. When a new job arrives, we look at the earliest time any server will be free. That time is the earliest possible start time for this job, given that all previously arrived jobs must be served before it (because of FIFO). However, is it always true that the earliest free time among servers is the start time for the next job? Consider if there are multiple servers, and a job arrives while some servers are free. Then it starts immediately on some free server; that start time is its arrival time, not necessarily the earliest free time (which could be less than arrival). But we use max(s, free_time) which handles that.
Now consider a scenario where there is a waiting job that arrived earlier, and a new job arrives later. The earlier job's start time is already determined as the earliest free time at the time it became head of queue. In our algorithm, we assign each job at arrival, so the earlier job's start time is computed when it arrived, and we used the earliest free time at that moment. That earliest free time might be later than the actual start time if later a server becomes free earlier? But that can't happen because the earliest free time at that moment is the earliest among all servers at that moment. Over time, servers may become free earlier if no other job is assigned? But all servers are already assigned to jobs? Actually, after we assign a job to a server, we push its finish time. The server's free time is then that finish time. That could be large. Later, if a new server becomes free earlier, could that cause the earlier job to be rescheduled to an earlier start? No, because the earlier job is already assigned to a specific server; it cannot switch servers. In a real FIFO queue, a job waiting in the queue is not assigned to a server until a server becomes free. So if a server becomes free earlier than expected, that would benefit the waiting job. But our assignment at arrival might lock the job to a server that becomes free later than another server that becomes free earlier but is assigned to a later job? Let's test: Suppose we have 2 servers. J1 arrives at time 0, p=100. J2 arrives at time 1, p=1. J3 arrives at time 2, p=100.
Real FIFO: Time0: J1 starts on server A (finish100). Server B idle. Time1: J2 arrives, server B idle, starts immediately, finishes at2. Time2: J3 arrives, server B just finished (free at2), so J3 starts on server B at2, finishes 102. So J3 finishes at102.
Our algorithm:
- J1: pop0 -> server A, start0, finish100, push100. Heap[0,100] (server B free at0)
- J2: pop0 -> server B, start1, finish2, push2. Heap[2,100]
- J3: pop2 -> server B (free at2), start2, finish102, push102. Heap[100,102]. Matches.
Now consider a scenario where the earlier job is long, and later jobs are short, but we might assign the long job to a server that becomes free later? Let's try to produce a counterexample:
Suppose we have 3 servers. Jobs: J1: s=0, p=100 (long) J2: s=1, p=10 (medium) J3: s=2, p=1 (short) J4: s=3, p=100 (long)
Real FIFO simulation: Time0: J1 starts on server A. Servers B and C idle. Time1: J2 arrives, starts on server B (idle). (finish11) Time2: J3 arrives, server C idle, starts immediately, finishes at3. Time3: J4 arrives. At time3, server C just finished (free), server A busy until100, server B busy until11. So J4 starts on server C at3, finishes103. Our algorithm:
- J1: pop0 -> A, start0, finish100, push100. Heap[0,0,100]? Actually initially 3 zeros. After pop one, push100, heap now contains [0,0,100] (two zeros).
- J2: pop0 -> B, start1, finish11, push11. Heap[0,11,100] (one zero left).
- J3: pop0 -> C, start2, finish3, push3. Heap[3,11,100].
- J4: pop3 -> C (since min=3), start=max(3,3)=3, finish103, push103. Heap[11,100,103]. Matches.
Now try to craft scenario where our assignment at arrival could lead to a job being assigned to a server that will finish later than another server that becomes free earlier, but that earlier server is assigned to a later job? That would violate FIFO because then the later job might start before the earlier job? But FIFO ensures order; if an earlier job is waiting, it should start before later jobs. So such assignment would be incorrect. Let's see if our algorithm could cause an earlier job to be assigned to a later server and a later job to an earlier server, resulting in later job starting earlier. Is that possible? Suppose we have jobs J1 (arrives at time t1) and J2 (arrives at t2 > t1). When J1 arrives, we pop the smallest free time, say free_a. So we assign J1 to server A with start = max(t1, free_a) and free time becomes start + p1. When J2 arrives, we pop the smallest free time again from the heap (which now includes server A's new free time and other servers). Could it be that the smallest free time at J2's arrival is from server B, and that free time is less than server A's free time? Possibly. But then J2 would be assigned to server B and start at that free time. However, if J1 is still waiting (i.e., its start time is later than its arrival because it was assigned to server A with a future start), could J2 start before J1? Let's examine. For J1 to be waiting, we must have had free_a > t1 at its arrival, meaning all servers were busy and the earliest free time was free_a. So free_a > t1. So J1 is scheduled to start at free_a. Now when J2 arrives at t2 > t1, what is the heap's min? It could be free_b (some other server) that is less than free_a? But if free_b < free_a, that would mean that at time when J1 arrived, the min free time was free_a, which was the smallest among all servers. So free_a <= free_b at that time. After assigning J1 to server A, we pushed its finish time (start+p1). Since start = free_a (because free_a > t1), its new free time = free_a + p1. That is likely > free_a. Meanwhile, server B's free time remains free_b (which was >= free_a at that time). Could free_b become less than free_a after J1's assignment? No, because free_b hasn't changed (server B wasn't assigned a new job, so its free time remains the same). Since free_b was >= free_a originally, and free_a increased to free_a + p1, now free_b might be less than free_a + p1, but it's still >= free_a? Actually free_b could be equal to free_a if there were multiple servers with same earliest free time. But if free_b > free_a originally, then free_b > free_a. After assignment, free_a becomes larger, so free_b might now be the smallest. But free_b is still > original free_a? Wait, original min free time was free_a. If there were multiple servers with free_a (tie), we popped one. The remaining ones still have free_a. So after popping, the heap still contains other servers with free_a (if any). So at J1's assignment, if there were multiple servers with the same earliest free time, we could assign J1 to one of them, and the others still have free_a. Then at J2's arrival, the smallest free time could be free_a (from another server) if that server is still free at that time (i.e., free_a <= t2). But if free_a > t2, then all servers are busy, and the smallest free time might be free_a (still) or possibly a server that became free earlier due to finishing a short job? But at J1's arrival, all servers had free times >= free_a. No server had a free time less than free_a. So after assigning J1, the other servers still have free times >= free_a (since we haven't changed them). The only server that changed (server A) now has a free time > free_a. So the smallest free time in the heap after assignment is min( free_a (others), free_a + p1, maybe other servers with free times > free_a). That min is free_a (if there is any other server with free_a). So the earliest free time remains free_a. Therefore, when J2 arrives, the min free time is free_a (or possibly less than free_a? No). So if free_a > t2, then J2 will also be assigned to a server with free time free_a (or maybe another server with free_a). That would mean J2's start = free_a (since free_a > t2). But then J2 would start at the same time as J1? But J1's start is free_a as well (since free_a > t1). So both would start at free_a? However, only one server becomes free at free_a? Actually if there were multiple servers with free time free_a, then at time free_a, more than one server becomes free. In that case, both J1 and J2 could start at free_a if there are enough servers. But J1 arrived earlier, J2 later. At time free_a, if two servers become free, then they could start both J1 and J2 simultaneously. That's allowed: J2 would start at the same time as J1, but that's okay because there are multiple servers. But could J2 start before J1? For J2 to start before J1, we would need a server to become free earlier than free_a. But we argued that after J1's assignment, the earliest free time remains free_a (unless some server's free time is reduced, which doesn't happen). So J2 cannot start before J1. Thus FIFO order preserved.
What if at J1's arrival, all servers were busy and we popped the smallest free time free_a, which belonged to server A. Suppose there were no other servers with free_a; all other servers had free times > free_a. So after assignment, the next smallest free time becomes free_b (the smallest among the remaining). That free_b is > free_a. So now the earliest free time becomes free_b. When J2 arrives at t2, if free_b <= t2? Possibly if t2 is large. But if free_b > t2, then J2 will be assigned to server B with start = free_b. That start time free_b is > free_a, so J2 starts after J1 (since J1 starts at free_a). So J2 doesn't start before J1. So order preserved.
Thus algorithm is correct.
Now we should consider if any job's start time could be earlier than its arrival? No because we take max.
One more nuance: The problem states: "If some video appeared at time s, then its recompressing can start at that very moment, immediately. Some videos can await recompressing when all the servers are busy. In this case, as soon as a server is available, it immediately starts recompressing another video. The videos that await recompressing go in a queue. If by the moment the videos started being recompressed some servers are available, then any of them starts recompressing the video." So indeed FIFO.
Now about initialization: Could there be any servers that are busy initially? No, they all start working at time 0, and before that no jobs.
Thus solution as described.
Now we can implement.
But we must be careful about input size and output. Use printf/scanf in C or fast cin/cout. Since we need to output up to 5e5 numbers, endl is slow; use '\n'.
Potential pitfall: When k is huge (500k) and n is small (like 1), initializing heap with k zeros may be wasteful but acceptable. But we can optimize by only pushing zeros as needed: maintain that if there are free servers, we treat free time as 0. For example, we can keep a counter of free servers, but then we'd need to manage which server becomes free when. Actually simpler: we can initially push k zeros. The memory for heap of 500k longs is about 4 MB (8 bytes each) = 4 MB, fine. Time to push 500k zeros is O(k) which is okay. So it's fine.
Alternatively, we can use a min-heap but only maintain at most k entries. Since we always pop then push, the size stays k. So it's fine.
One more nuance: In C++, priority_queue with greater comparator yields min-heap. We need to include or just use vector and greater.
Implementation:
int main() { int n, k; scanf("%d %d", &n, &k); priority_queue<long long, vector, greater> pq; for (int i = 0; i < k; ++i) pq.push(0); for (int i = 0; i < n; ++i) { long long s, m; scanf("%lld %lld", &s, &m); long long t = pq.top(); pq.pop(); long long start = s > t ? s : t; long long finish = start + m; pq.push(finish); printf("%lld\n", finish); } return 0; }
That's all.
But let's test with some custom cases:
Case: n=1,k=5, s=10,m=5 => heap has zeros. t=0, start=10, finish=15. Output 15. Makes sense.
Case: n=5,k=5, all s=0,m=1..5? Actually s distinct, but if s all zero? Problem says all s_i distinct and increasing, so cannot have same s. So first s=0 allowed? It says 1 ≤ si ≤ 1e9, so minimal is 1. So s>=1. So no zero.
Edge case: k=500000, n=500000. Our heap initial size 500k, each operation log(500k) ~ 19, total 9.5 million operations, fine.
Now about integer overflow: We use long long (64-bit). In C++, long long is at least 64-bit. The sum may be up to about 5e14, which fits in 2^63-1 (~9e18). So safe.
Thus solution is complete.
However, we need to consider the possibility that k could be larger than n. In that case, we still push k zeros, but we will only pop n times, leaving k-n zeros in heap. That's fine.
Now we can finalize.
But wait, is there any hidden nuance about "videos are recompressed in the order they appear"? The statement says: "All videos appear at different moments of time and they are recompressed in the order they appear." That directly says FIFO.
Now confirm that our algorithm respects that order even when a server becomes free exactly at the arrival of a new job and there is a waiting job. Example: Suppose J1 arrives at t=0, p=10, k=1. J2 arrives at t=5, p=1. J3 arrives at t=6, p=2. With k=1, FIFO: J1 start0 finish10, J2 start10 finish11, J3 start11 finish13. Our algorithm: heap[0] initially. J1: pop0, start0, finish10, push10. J2: pop10, start=max(5,10)=10, finish11, push11. J3: pop11, start=max(6,11)=11, finish13, push13. Works.
Now consider k=2, J1:0,10; J2:5,10; J3:5? Actually s distinct, so J2 and J3 cannot have same s. Let's do J1:0,10; J2:1,10; J3:2,1. FIFO: At 0, J1 starts on A. Server B idle. At 1, J2 arrives, B idle, starts on B. Both busy until 10 and 11? Actually J1 finishes at10, J2 finishes at11. At 2, J3 arrives, both busy, waits. At 10, A free, J3 starts, finishes 11. So J3 finishes at11. Our algorithm: J1: start0, finish10, push10; heap[0,10] (since other server 0). J2: pop0, start=1, finish11, push11; heap[10,11]. J3: pop10, start=max(2,10)=10, finish11, push11; heap[11,11]. Works.
Now consider case where a job arrives exactly when a server becomes free, but there is also a waiting job. For example: J1:0,5; J2:3,10; J3:5,1; k=2. FIFO: At 0, J1 starts on A (finish5). B idle. At 3, J2 arrives, B idle, starts on B (finish13). At 5, J3 arrives. At that exact moment, A becomes free (finishes at5). So there is an available server at time5. So J3 starts immediately on A at5, finishes6. So J3 finishes at6. Our algorithm: J1: start0, finish5, push5; heap[0,5]? Actually after J1: heap[0,5] (other server 0). J2: pop0, start=3, finish13, push13; heap[5,13]. J3: pop5, start=max(5,5)=5, finish6, push6; heap[6,13]. Works.
Now consider scenario where two servers become free at the same time and there are multiple waiting jobs. Our algorithm will assign them in order because when each job arrived, it was assigned to a server that would be free at some time; but what if two jobs are waiting and two servers become free simultaneously? Our algorithm, when processing the later job after the earlier, will assign it to the server that becomes free later? Actually let's simulate: k=2. Jobs: J1:0,5; J2:1,5; J3:2,5; J4:3,5. Let's manually compute FIFO: Time0: J1 starts on A (finish5). B idle. Time1: J2 arrives, B idle, starts on B (finish6? Actually p=5, start1 -> finish6). So B finishes at6? Wait start=1, finish=6. So B finishes at6. Time2: J3 arrives. Both servers busy (A until5, B until6). So J3 waits. Time3: J4 arrives. Both still busy? At time3, A busy until5, B busy until6. So J4 waits. Now queue: J3 then J4. At time5, A becomes free. Takes J3, starts at5, finishes10. At time6, B becomes free. Takes J4, starts at6, finishes11. So finish: J1:5, J2:6, J3:10, J4:11. Our algorithm:
- J1: pop0 -> A, start0, finish5, push5. heap[0,5] (B free at0)
- J2: pop0 -> B, start1, finish6, push6. heap[5,6]
- J3: pop5 -> A? Actually min=5 (since 5<=2? No 5 >2, so start=5), finish10, push10. heap[6,10]
- J4: pop6 -> B? min=6, start=max(3,6)=6, finish11, push11. heap[10,11] Output: 5,6,10,11. matches.
Now consider scenario where after J3 is assigned to A with start5, J4 is assigned to B with start6. That's correct.
Now consider scenario where there are more than two servers, and multiple become free at same time and multiple waiting jobs. Our algorithm processes jobs in arrival order, so each job gets assigned to the current minimum free time. If multiple servers have the same free time (say free_time = T), then the first waiting job will pop that T (one of them) and be assigned start T, pushing new finish. The next waiting job will pop the next free time, which might still be T if there were multiple servers with free time T (since we popped only one). So it will also get start T. So multiple jobs can start at same time, which is correct for FIFO: when multiple servers free simultaneously, they all take the next jobs from the queue in order. So our algorithm respects that.
Thus the algorithm is correct.
Now think about memory and time constraints: O(n log k) works.
Now, is there any scenario where using a heap of size k might cause a performance issue because k up to 5e5 and n up to 5e5, and each operation is O(log k) ~ 19, so total operations ~ 10 million, which is fine.
One more nuance: The heap always contains exactly k elements. Initially k zeros. For each job, we pop and push, so still k. So if n < k, we only do n pops and pushes, leaving k-n zeros in heap. That's okay.
But we could also start with an empty heap and maintain a count of idle servers. Another common optimization: Use a priority queue for busy servers only, and a counter for idle ones. When a job arrives, if there are idle servers, start immediately with start = s, and decrement idle count, and push the finish time onto busy heap. If no idle servers, pop the smallest finish time from busy heap, compute start = max(s, that finish), then push new finish. However, you need to also account that after popping, that server becomes busy again, so idle count doesn't change. That approach uses a heap of size <= k, but average size maybe less. But either is fine.
But simpler: Just have heap of size k. But note: if k is huge and n is small, we are pushing many zeros that are never used? That's okay: 500k zeros is trivial.
Thus solution stands.
Now consider the possibility of using 64-bit for all times. Input s and m are up to 1e9, but we need to multiply? Not needed; m is already in seconds. So direct addition.
Now implement.
But careful: The problem statement: "Each server takes one second to recompress a one minute fragment. Thus, any server takes m seconds to recompress a m minute video." So m_i is minutes? But given as integer, and we treat as seconds directly. That's correct.
Now code.
Now we produce final answer.
However, I've seen similar problems where they ask for finishing times, and the solution is as above.
Now we should also consider if the order of output matters: They want each ei on separate line.
Now final answer: C++ code.
We'll also include fast I/O.
Now I think that's all.
But before finalizing, double-check with some random tests using a brute force simulation for small n,k to ensure correctness.
We can think of a small brute force: simulate events: maintain a queue of waiting jobs, and an array of server free times. For each arrival in order, and each completion event. But we trust the known approach.
Potential pitfalls: The heap approach relies on the fact that jobs are processed in order of arrival. If we process out of order, it fails. But input is sorted.
Now regarding initial free times: Since servers start at time 0, they are free at time 0. That is fine even if all s_i >=1.
Now some might think that if we push zeros for all servers, then for the first job we pop a zero, but if k is huge, we may pop a zero that represents a server that is free, but we also have many other zeros. That's fine.
Now consider the possibility that a server becomes free at time 0, but job arrives at time >0, we assign it to that server, start = s. That's fine.
Now think about case where a server's free time is far in future, but we still push it onto heap. That's fine.
Now final code.
But the problem constraints: n,k up to 5e5. Input reading should be efficient. Use scanf/printf.
Let's produce final answer.
But we should also consider using an array for heap? No, STL priority_queue is fine.
One more thought: The algorithm as described will produce correct finish times for all jobs, but we need to print them in the order of input. Since we process in order, we can print directly.
Now about the possibility of using 64-bit with printf: "%lld" works on most judges. Or use cout with long long.
Now final solution is straightforward.
But let's not forget to handle if k is 0? But k >=1 per constraints.
Now done.
Now, for completeness, we can also implement using a multiset, but priority_queue is simpler.
Thus answer.
But wait, is there any trick about the fact that "they are recompressed in the order they appear"? Could it mean that if two videos appear at the same time? But input says distinct si, so no.
Alright.
Now deliver final solution.
We might also think about an alternative approach: using a queue and a priority queue for server free times, but same.
Now code:
#include #include #include #include using namespace std;
int main() { int n, k; scanf("%d %d", &n, &k); priority_queue<long long, vector, greater> pq; for (int i = 0; i < k; ++i) { pq.push(0); } for (int i = 0; i < n; ++i) { long long s, m; scanf("%lld %lld", &s, &m); long long t = pq.top(); pq.pop(); long long start = (s > t) ? s : t; long long finish = start + m; pq.push(finish); printf("%lld\n", finish); } return 0; }
That's it.
But we can also avoid ternary by using max.
Now about reading: Some judges might require "unsigned long long"? But not needed.
Now we should test with sample.
Sample 1: 3 2 1 5 2 5 3 5 Processing: pq: [0,0] i1: t=0, start=1, finish=6, push6 -> [0,6] i2: t=0, start=2, finish=7, push7 -> [6,7] i3: t=6, start=6, finish=11 -> output 6,7,11. matches.
Sample 2: as before.
Now we could also consider a test where k is large and n is 1: e.g., 1 5, 10 5 -> output 15.
Now done.
Now we can produce final answer with explanation.
But note: In the problem statement, they mention m minutes, and m seconds to recompress. Actually they said "each server takes one second to recompress a one minute fragment. Thus, any server takes m seconds to recompress a m minute video." So m_i is in minutes? But input gives integer mi. So we treat as seconds. That's correct.
Now final answer.
I'll produce final solution in C++. ```cpp
#include #include #include #include
using namespace std;
int main() { int n, k; scanf("%d %d", &n, &k);
// Min-heap of times when servers become free (initially all at 0) priority_queue<long long, vector<long long>, greater<long long>> free_times; for (int i = 0; i < k; ++i) { free_times.push(0); } for (int i = 0; i < n; ++i) { long long s, m; scanf("%lld %lld", &s, &m); long long t = free_times.top(); // earliest free server free_times.pop(); long long start = s > t ? s : t; // when this video actually starts long long finish = start + m; // finishing moment free_times.push(finish); printf("%lld\n", finish); } return 0;}