题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6119

题意:中文题面。

解法:先处理可能交叉的区间,然后容易发现满足双指针的特性。

//HDU 6119
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
const int maxn = 1e5+10;
pair<LL,LL>p[maxn];
LL n,m,sum[maxn]; int main()
{
while(~scanf("%lld%lld",&n,&m))
{
for(int i=1; i<=n; i++) scanf("%lld%lld",&p[i].first,&p[i].second);
sort(p+1,p+n+1);
int cnt=0;
for(int i=1; i<=n; i++){
LL l=i,r=i+1,last=p[i].second;
while(r<=n&&p[r].first<=last){
last=max(last,p[r].second),r++;
}
r--;
p[cnt++]=make_pair(p[l].first,last);
i=r;
}
sum[0]=0;
for(int i=1; i<cnt; i++){
sum[i]=sum[i-1]+p[i].first-p[i-1].second-1;
}
LL ans=m;
int r=0;
for(int l=0; r<cnt&&l<cnt; l++){
while(sum[r]-sum[l]<=m&&r<cnt) r++;
LL x = m-(sum[r-1]-sum[l]);
ans = max(ans, p[r-1].second-p[l].first+1+x);
}
printf("%lld\n", ans);
}
return 0;
}

最新文章

  1. Canvas基础认识
  2. jquery this 和 event.target 区别
  3. CSS之viewport 1
  4. Linux系统下安装MongoDB 指南
  5. 用c#开发微信 (12) 微统计 - 阅读分享统计系统 2 业务逻辑实现
  6. JQuery知识快览之四—样式
  7. Linux设置禁止用户登陆
  8. 【JAVA - SSM】之SSM入门项目的搭建
  9. php基础知识【函数】(9)数学和对象类函数
  10. SELECT--UNION,UNION ALL,MINUS, INTERSECT,EXISTS
  11. werfault进程使用CPU率高
  12. matlab 写文件
  13. ELK对Tomcat日志双管齐下-告警触发/Kibana日志展示
  14. inno安装客户端,写注册表url调用客户端
  15. Nginx 安装配置
  16. 开源性能测试工具Locust使用篇(二)
  17. win10 图标异常 ,重命名后,图标不显示,名字错乱。
  18. pandas 常用清洗数据(三)排序,去重
  19. [shiro学习笔记]第四节 使用源码生成Shiro的CHM格式的API文档
  20. LeetCode152:Maximum Product Subarray

热门文章

  1. Python替换字符串中的反斜杠\
  2. 转:Conjugate prior-共轭先验的解释
  3. BZOJ4868:[SHOI2017]期末考试——题解
  4. BZOJ1458 士兵占领 【带上下界网络流】
  5. 洛谷 P4592 [TJOI2018]异或 解题报告
  6. HDOJ(HDU).2044-2049 递推专题
  7. 命令:ln 使用方法
  8. AtCoder Regular Contest 081 E - Don&#39;t Be a Subsequence(字符串DP)
  9. POI 10.28
  10. jdbcType和javaType