Acwing-4455. 出行计划

 暴力解法TLE了，过了70%的数据

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; ++ i) scanf("%d%d", &a[i], &b[i]);
    
    while (m --)
    {
        int q;
        scanf("%d", &q);
        
        int res = 0;
        for (int i = 0; i < n; ++ i)
        {
            if (q + k > a[i]) continue;
            if (q + k + b[i] - 1 >= a[i]) res ++;
        }
        
        printf("%d\n", res);
    }
    
    return 0;
}

正解：t时刻做核酸，可以在[t + k, t + k + c - 1]进入某个场所，其中c为进入场所时所需的单位时间数。若在ti时刻进入某场所，即要求ti >= t + k，且ti <= t + k + c - 1，可以解得ti - k - c + 1 <= t <= ti - k。所以若在时刻q做了核酸，那么可以进入场所的区间为[ti - k - c + 1, ti - k]，即只需看时间q落在多少个区间内部，然后让这个区间内所有数加一即可，这可以利用差分来做。对差分数组求前缀和数组即可得到原数组。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 200010;

int b[N];
int n, m, k;

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