CSP 202203-2 出行计划 C++ 100

2023-01-05

题目

【问题描述】最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。具体来时，如果在t时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。这里我们假定等待核酸检测结果需要k个单位时间，即在t+k时刻可以获得结果。如果一个场所要求持24个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第t+k时刻到第t+k+23时刻进入该场所。小C按时间顺序列出接下来的n项出行计划，其中第i项(1≤i≤n)可以概括为： t时刻进入某场所，该场所需持有ci个单位时间内的核酸检测结果入内，其中0<ci≤2×10^5。为了合理安排核酸检测时间，试根据小C的出行计划，回答如下查询： ·如果在q时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足？这样的查询共有m个，分别为q1，q2,···,qm;查询之间互不影响。

【输入格式】输入的第一行包含空格分隔的三个正整数n、m和k,分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。接下来输入n行，其中每行包含用空格分隔的两个正整数ti、ci,表示一项出行计划：出行计划按时间顺序给出，满足0<t1≤t2≤···≤tn≤2×10^5. 最后输入 m 行，每行仅包含一个正整数qi，表示一个查询。m个查询亦按照时间顺序给出，满足 0<q1<q2<···<qm≤2×10^5。

【输出格式】输出共 m 行，每行一个整数，表示对应查询的答案。

【样例输入】

【样例输出】

1
2

3
3

代码

#include <iostream>

using namespace std;

const int N = 4e5+5;
int main()
{
    int t[100000],c[100000];
    int b[N]={0};
    int n,m,k,q,left,right;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
    {
        cin>>t[i]>>c[i];
        left=t[i]-c[i]+1;
        left = left>0?left:1;
        right=t[i];
        b[left]++;
        b[right+1]--;
    }

    for(int i=1;i<N;i++)
    {
        b[i]=b[i]+b[i-1];
    }
    while(m--)
    {
        cin>>q;
        cout<<b[q+k]<<endl;
    }
    return 0;
}