Bzoj 3126[Usaco2013 Open]Photo 题解
3126: [Usaco2013 Open]Photo
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 335 Solved: 169
[Submit][Status][Discuss]
Description
Farmer John has decided to assemble a panoramic photo of a lineup of his N cows (1 <= N <= 200,000), which, as always, are conveniently numbered from 1..N. Accordingly, he snapped M (1 <= M <= 100,000) photos, each covering a contiguous range of cows: photo i contains cows a_i through b_i inclusive. The photos collectively may not necessarily cover every single cow. After taking his photos, FJ notices a very interesting phenomenon: each photo he took contains exactly one cow with spots! FJ was aware that he had some number of spotted cows in his herd, but he had never actually counted them. Based on his photos, please determine the maximum possible number of spotted cows that could exist in his herd. Output -1 if there is no possible assignment of spots to cows consistent with FJ's photographic results.
给你一个n长度的数轴和m个区间,每个区间里有且仅有一个点,问能有多少个点
Input
* Line 1: Two integers N and M.
* Lines 2..M+1: Line i+1 contains a_i and b_i.
Output
* Line 1: The maximum possible number of spotted cows on FJ's farm, or -1 if there is no possible solution.
Sample Input
1 4
2 5
3 4
INPUT DETAILS: There are 5 cows and 3 photos. The first photo contains cows 1 through 4, etc.
Sample Output
OUTPUT DETAILS: From the last photo, we know that either cow 3 or cow 4 must be spotted. By choosing either of these, we satisfy the first two photos as well
#pragma GCC optimze("O3")
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#define N 200005
using namespace std;
int n,m,r[N],l[N],q[N*],en,hea=,f[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n+;i++)
r[i]=i-;
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
l[y+]=max(l[y+],x);
r[y]=min(r[y],x-);
}
for(int i=;i<=n+;i++)
l[i]=max(l[i],l[i-]);
for(int i=n;i>;i--)
r[i]=min(r[i],r[i+]);
en++;
q[en]=;
for(int i=;i<=n+;i++)
{
for(int j=r[i-]+;j<=r[i];j++)
{
while(hea<=en&&f[q[en]]<f[j])en--;
en++;
q[en]=j;
}
while(hea<=en&&q[hea]<l[i])hea++;
if(hea>en)
f[i]=-0x7ffffff;
else
f[i]=f[q[hea]]+;
}
if(f[n+]>=)printf("%d\n",f[n+]-);
else
printf("-1\n");
return ;
}
最新文章
- Flash调用麦克风
- .NET 4.0 中超长路径超长文件名的问题
- (20)odoo中的action
- 008sudo用户管理
- UML 行为图之用例图 总结
- vijos1009:扩展欧几里得算法
- 【Java基础】 static
- Java入门(2) —— 变量详解、运算符、定义类和定义方法以及方法的调用
- 0323-DOM基础操作
- CopyOnWriteArrayList源码解析
- python+selenium运行时,提示元素不可见
- C# 查看EF生成的SQL语句
- EF Fluent API
- python-Django-01基础配置
- ubuntu 下 go 语言调试器 dlv 的安装
- MT【179】最大最小老问题
- (转)C/C++ 程序设计员应聘常见 面试笔试 试题深入剖析
- 【c++基础】多个txt文件合并到一个文件的几种方式
- HHvm建站环境搭建方法:Nginx,Mariadb,hhvm及lnmp/lamp安装部署
- 开源项目Log4j
热门文章
- linux的自动化操作相关使用方法汇总 专题
- ArcGIS for Desktop入门教程_第二章_Desktop简介 - ArcGIS知乎-新一代ArcGIS问答社区
- Oracle序列使用:建立、删除、使用
- Windows应用程序文件说明
- Ruby已经慢慢走向衰退了,那些年代久远而且小众的语言没有翻身的可能性
- 通过Graphics对象获取它所属的Control
- 我们检测到您的浏览器不兼容传输层安全协议 (TLS) 1.1 或更高版本,此协议在 Internet 上用于确保您通信的安全性。
- Java集合 ArrayList原理及使用
- MacOS平台上编译 hadoop 3.1.2 源码
- 【转】三次握手——https为什么更安全