【JZOJ5264】化学

Description

Input

Output

Sample Input

3 10
1 2 10

Sample Output

5

Hint

题解:

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

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <set>
#define MAXN 50010
using 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<data> s;
multiset<data>::iterator it;
int n,m,have; void cl(){
memset(qv,,sizeof(qv));
memset(aum,,sizeof(aum));
s.clear();
} bool cmp1(hhh x,hhh y){
if(x.x<y.x) return ;
return ;
} bool cmp2(hhhh x,hhhh y){
if(x.x<y.x) return ;
return ;
} int getit(int hh){
for(int i=n;i>=;i--) if(qv[i].x<=hh) return i;
return ;
} int getmin(int r,int now){
int numm=(<<),id=;
for(int i=;i<=r;i++){
if(qv[i].num==) continue;
if(qv[i].y<aum[now].y) continue;
if(numm>qv[i].y) numm=qv[i].y,id=i;
}
return id;
} void work(){
cl();
scanf("%d%d",&n,&m);for(int i=;i<=MAXN-;i++) qv[i].x=<<;
for(int i=;i<=n;i++) aum[i].read();
for(int i=;i<=m;i++) qv[i].read();
have=m;
sort(aum+,aum+n,cmp1);
sort(qv+,qv+m+,cmp2);
if(qv[].x>aum[].x){puts("No");return;}
int id=;s.insert((data){qv[].y,qv[].num});
for(int i=;i<=n;i++){
int x=aum[i].x,y=aum[i].y,num=aum[i].num;
while(qv[id+].x<=x){
id++; if(qv[id].num!=) s.insert((data){qv[id].y,qv[id].num});
}
while(num){
it=s.lower_bound((data){y,});
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=;
if(num!=&&have==){puts("No");return;}
}
if(have==&&i!=n){puts("No");return;}
}
puts("Yes");
} int main()
{
int t;cin>>t;
while(t--) work();
return ;
}

最新文章

  1. 微信公众平台应用开发:方法、技巧与案例--柳峰,Java语言版本
  2. 使用MeanJS Yeoman Generator
  3. fsutil
  4. Linux下Docker安装
  5. C#操作INI配置文件示例
  6. cf B. Color the Fence
  7. VS快捷编码方式
  8. 高质量程序设计指南C/C++语言——内存管理
  9. Jenkins中集成python,支持参数生成Makefile文件
  10. 转: 【Java并发编程】之五:volatile变量修饰符—意料之外的问题(含代码)
  11. ThinkPHP中对系统常量的使用
  12. 深入理解Linux内核 学习笔记(4)
  13. LOJ#6374 网格
  14. C#特性之数据类型
  15. fullstack
  16. js混淆加密,通过混淆Js代码让别人(很难)无法还原
  17. HTML5 Canvas,WebGL,CSS Shaders,GLSL的暧昧关系
  18. 最快下载速度100Mbps!4G LTE技术全解析
  19. XML第一次简单入门(Lab分析)
  20. 【四边形不等式】noi95- 合并石子

热门文章

  1. 【Nginx】 中的配置命令
  2. 慕课网jojo老师的Angular课程中遇到的问题
  3. ReentrantLock——可重入锁的实现原理
  4. WPF 自定义UI控件学习
  5. ActiveMQ的安装与使用。
  6. 即时聊天APP(三) - 注册和登陆
  7. PHP秒杀系统 高并发 高性能的极致挑战 下载
  8. OkHttp3使用教程,实现get、post请求发送,自动重试,打印响应日志。
  9. 15 (OC)* UIGesture
  10. Hadoop 之 HDFS的使用