solution
对于每个糖糖考虑计算他是不是会被消灭。一个组的糖糖会被消灭仅后面存在一个组的糖糖满足,表示前秒总共增加的能量值。移项得。所以把每个糖糖的能量值都变为。然后从后向前枚举的过程中分别统计两个后面的最大值。判断当前点是否会被消灭。
code
/* * @Author: wxyww * @Date: 2020-04-20 17:25:13 * @Last Modified time: 2020-04-20 17:37:11 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 1000010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int mx[2],col[N],a[N],sum[N]; int main() { int T = read(); while(T--) { int n = read(),m = read(); int ans = n; for(int i = 1;i <= n;++i) { col[i] = read();a[i] = read(); } memset(sum,0,sizeof(sum)); for(int i = 1;i <= m;++i) sum[read()]++; for(int i = 1;i <= n;++i) { sum[i] += sum[i - 1]; a[i] -= sum[i - 1]; } mx[0] = mx[1] = -10000000; for(int i = n;i >= 1;--i) { if(mx[col[i] ^ 1] > a[i]) { ans--; } mx[col[i]] = max(mx[col[i]],a[i]); } printf("%d\n",ans); } return 0; }