特别提示一下,本题开个全局比较好,我开局部的一直wa。全局就过了。
题解:我们如果正着来做没有那么好做,过程极度复杂,那么就逆向思维来看,如果我们不是一组的那么是不是其他组比我当前的组小的应该全部被消灭,所以,我们可以直接处理每个时间之后应该增加的攻击力,然后,再去倒序处理一下,每次都找当前最大的 ,比它小的就是会被消灭,那么是不是我们所有人-消灭的=存活的。
#include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define debug(x) cout << #x << ": " << x << endl; #define debug1(x) cout<<"xxx"<<endl; #define ll long long #define ull unsigned long long #pragma GCC optimize("Ofast","inline","-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #define mse(a,b) memset(a,b,sizeof b); using namespace std; const int maxx=1e6+100; const int mod=1e9+7; struct node { ll a1,b1; }; node ans[500500]; ll bb[50050]; int main() { fio; ll a; scanf("%lld",&a); while(a--) { memset(bb,0,sizeof bb); ll n,m; scanf("%lld%lld",&n,&m); for(ll i=1; i<=n; i++) scanf("%lld%lld",&ans[i].a1,&ans[i].b1); for(ll i=1; i<=m; i++) { ll x; scanf("%lld",&x); bb[x]++; } for(ll i=n; i>=1; i--) { bb[i]+=bb[i+1], ans[i].b1+=bb[i]; } ll ma1=-1e9,ma0=-1e9; ll sum=0; for(ll i=n; i>=1; i--) { if(ans[i].a1==0) { ma0=max(ma0,ans[i].b1); if(ma1>ans[i].b1) { sum++; } } else { ma1=max(ma1,ans[i].b1); if(ma0>ans[i].b1) sum++; } } printf("%lld\n",n-sum); } return 0; }