【JZOJ5264】化学

Description

Input

Output

Sample Input

3 10

1 2 10

Sample Output

5

Hint

 

题解:

　　这个题目又是一道贪心题,我们考虑将区间当成区间上的点(l对应x,r对应y),所以我们对于每种点,我们要寻找的点为于以当前这个点为原点的左上项限上,所在我们将两种点按照x来排序,每次一个一处理,每次取左上方项限中y最小的点就可以multset维护一下就可以了.

 

代码:

#include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define MAXN 50010using namespace std;struct hhh{ int x,y,num; void read(){ scanf("%d%d%d",&x,&y,&num); }}aum[MAXN];struct hhhh{ int x,y,num; void read(){ scanf("%d%d%d",&x,&y,&num); }}qv[MAXN];struct data{ int y,num; bool operator < (const data x)const{ return x.y>y; }};multiset
                 s;multiset::iterator it;int n,m,have;void cl(){ memset(qv,0,sizeof(qv)); memset(aum,0,sizeof(aum)); s.clear();}bool cmp1(hhh x,hhh y){ if(x.x
                  
                   =1;i--) if(qv[i].x<=hh) return i; return 0;}int getmin(int r,int now){ int numm=(1<<30),id=0; for(int i=1;i<=r;i++){ if(qv[i].num==0) continue; if(qv[i].y
                   
                    qv[i].y) numm=qv[i].y,id=i; } return id;}void work(){ cl(); scanf("%d%d",&n,&m);for(int i=1;i<=MAXN-1;i++) qv[i].x=1<<30; for(int i=1;i<=n;i++) aum[i].read(); for(int i=1;i<=m;i++) qv[i].read(); have=m; sort(aum+1,aum+n,cmp1); sort(qv+1,qv+m+1,cmp2); if(qv[1].x>aum[1].x){puts("No");return;} int id=1;s.insert((data){qv[1].y,qv[1].num}); for(int i=1;i<=n;i++){ int x=aum[i].x,y=aum[i].y,num=aum[i].num; while(qv[id+1].x<=x){ id++; if(qv[id].num!=0) s.insert((data){qv[id].y,qv[id].num}); } while(num){ it=s.lower_bound((data){y,1}); if(it==s.end()){puts("No");return;} data xx=*it;int numm=xx.num; if(num>=numm) num-=numm,s.erase(it),have--; else s.erase(it),s.insert((data){xx.y,numm-num}),num=0; if(num!=0&&have==0){puts("No");return;} } if(have==0&&i!=n){puts("No");return;} } puts("Yes");}int main(){ int t;cin>>t; while(t--) work(); return 0;}