暴力

#include <iostream>

using namespace std;

const int N = 100010;
int n, m, k;
int t[N], c[N];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; i ++) scanf("%d%d", &t[i], &c[i]);

    while (m --) {
        int q;
        scanf("%d", &q);
        int res = 0;
        int l = q + k;
        for (int i = 0; i < n; i ++) {
            int r = l + c[i] - 1;
            if (t[i] >= l && t[i] <= r) res ++;
        }
        printf("%d\n", res);
    }

    return 0;
}

差分

对于某一个计划，当 q+k<=ti<=q+k+ci-1
变形得：ti-k-ci+1<=q<=ti-k
即只要在[ti-k-ci+1, ti-k]时间段内开始核酸检测，那么当前计划i就可以完成
所以可以用差分来解决
a[i]表示在第i时刻做核酸检测，有a[i]个计划可以完成，b[i]则是a[i]的差分数组
对于每一个事件i，只要时刻j满足[ti-k-ci+1, ti-k]这个区间
那么就将a[j]都加上1，表示在a[j]时刻开始做核酸检测可以完成的出行计划数加一

#include<iostream>

using namespace std;

const int N = 200010;

int n, m, k;
int t[N], c[N];
int a[N], b[N];

void insert(int l, int r, int x) {
    b[l] += x;
    b[r + 1] -= x;
}

int main() {

    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i ++) scanf("%d%d", &t[i], &c[i]);

    // 预处理
    for (int i = 1; i <= n; i ++) {
        int l = max(t[i] - k - c[i] + 1, 1), r = t[i] - k;
        if (r < 1) continue;   // r<1则说明该事件不可能完成  
        insert(l, r, 1);
    }

    for (int i = 1; i < N; i ++) a[i] = a[i - 1] + b[i];

    while (m -- ) {
        int q;
        scanf("%d", &q);
        printf("%d\n", a[q]);
    }

    return 0;
}