题目大意

略。

题解

容易想到按秒处理。发现前 个能力值加一可以转化为后面 个能力值减一。

于是维护到当前时间为止，当前位置及后面位置能力值被削减的量。之后就是简单的用两个堆处理一下即可。

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int a[50005], b[50005];
int cnt[50005];
priority_queue<int, vector<int>, greater<int> > pq[2]; 
void init(){
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read(), b[i] = read();
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= m; ++i)
        ++cnt[read()];
}
void solve(){
    int cur = 0;
    for (int i = 1; i <= n; ++i){
        int oppo = a[i] ^ 1;
        while (!pq[oppo].empty() && pq[oppo].top() < b[i] - cur)
            pq[oppo].pop();
        pq[a[i]].push(b[i] - cur);
        cur += cnt[i];
    }
    int ans = pq[0].size() + pq[1].size();
    printf("%d\n", ans);
    while (!pq[0].empty()) pq[0].pop();
    while (!pq[1].empty()) pq[1].pop();
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}