专栏首页算法修养Code Forces 644B Processing Queries

Code Forces 644B Processing Queries

B. Processing Queries time limit per test5 seconds memory limit per test256 megabytes inputstandard input outputstandard output In this problem you have to simulate the workflow of one-thread server. There are n queries to process, the i-th will be received at moment ti and needs to be processed for di units of time. All ti are guaranteed to be distinct.

When a query appears server may react in three possible ways:

If server is free and query queue is empty, then server immediately starts to process this query. If server is busy and there are less than b queries in the queue, then new query is added to the end of the queue. If server is busy and there are already b queries pending in the queue, then new query is just rejected and will never be processed. As soon as server finished to process some query, it picks new one from the queue (if it’s not empty, of course). If a new query comes at some moment x, and the server finishes to process another query at exactly the same moment, we consider that first query is picked from the queue and only then new query appears.

For each query find the moment when the server will finish to process it or print -1 if this query will be rejected.

Input The first line of the input contains two integers n and b (1 ≤ n, b ≤ 200 000) — the number of queries and the maximum possible size of the query queue.

Then follow n lines with queries descriptions (in chronological order). Each description consists of two integers ti and di (1 ≤ ti, di ≤ 109), where ti is the moment of time when the i-th query appears and di is the time server needs to process it. It is guaranteed that ti - 1 < ti for all i > 1.

Output Print the sequence of n integers e1, e2, …, en, where ei is the moment the server will finish to process the i-th query (queries are numbered in the order they appear in the input) or  - 1 if the corresponding query will be rejected.

Examples input 5 1 2 9 4 8 10 9 15 2 19 1 output 11 19 -1 21 22 input 4 1 2 8 4 8 10 9 15 2 output 10 18 27 -1

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <queue>

using namespace std;
#define MAX 200000
struct Node
{
    int id;
    long long int st;
    long long int time;
}a[MAX+5];
int cmp(Node a,Node b)
{
    return a.st<b.st;
}
queue<Node> q;
long long int ans[MAX+5];
int n,b;
int main()
{
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&a[i].st,&a[i].time);
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    int i=2;
    long long int now=a[1].st+a[1].time;
    ans[1]=now;
    while(1)
    {
        if(i>n&&q.size()==0)
            break;
        while(i<=n)
        {
            if(a[i].st>=now)
                break;
            if(q.size()>=b)
                ans[a[i++].id]=-1;
            else
            {
                q.push(a[i++]);
            }
        }
        if(q.size()==0)
        {now=a[i].st+a[i].time;ans[i]=now;i++;continue;}
        Node term=q.front();
        q.pop();
        now+=term.time;
        ans[term.id]=now;
    }
    for(int i=1;i<=n;i++)
    {
        if(i==n)
            printf("%lld\n",ans[i]);
        else
            printf("%lld ",ans[i]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ-1179 Polygon (动态规划)

    Polygon Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 5293...

    ShenduCC
  • PAT 1018 Public Bike Management(Dijkstra 最短路)

    1018. Public Bike Management (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16...

    ShenduCC
  • POJ-1143(状态压缩)

    Number Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: ...

    ShenduCC
  • 06-图2 Saving James Bond - Easy Version

    题目来源:http://pta.patest.cn/pta/test/18/exam/4/question/625 This time let us consi...

    llhthinker
  • Android 大文件切割与合并的实现代码

    由于公司的业务,硬生生的把ios开发的我,掰成了android!关于上传文件的需求处理,做了一个Java的简单封装 DocumentManagement 。其中...

    砸漏
  • Python基础--webbrowser

    The webbrowser module provides a high-level interface to allow displaying Web-ba...

    py3study
  • 浙江大学计算机与软件学院2019年保研上机模拟练习

    A happy number is defined by the following process: Starting with any positive i...

    glm233
  • HDUOJ---2642Stars(二维树状数组)

    Stars Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/65536 K (Jav...

    Gxjun
  • leetcode: 53. Maximum Subarray

    JNingWei
  • poj-1207 THE 3n+1 problem

    Problems in Computer Science are often classified as belonging to a certain clas...

    瑾诺学长

扫码关注云+社区

领取腾讯云代金券