思路:

考虑到补签卡一定是连续放置才更优,所以直接根据起始位置枚举。预先处理区间之间的gap的前缀和,在枚举过程中二分即可。复杂度O(nlog(n))。

实现:

 #include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll; const ll INF = 0x3f3f3f3f; int main()
{
int n, m;
while (scanf("%d %d", &n, &m) != EOF)
{
vector<pair<int, int>> v;
int x, y;
for (int i = ; i < n; i++)
{
scanf("%d %d", &x, &y);
v.push_back(pair<int, int>(x, y));
}
sort(v.begin(), v.end());
vector<pair<int, int>> res;
res.push_back(v[]);
for (int i = ; i < v.size(); i++)
{
if (v[i].first > res.back().second + ) res.push_back(v[i]);
else res.back().second = max(res.back().second, v[i].second);
}
vector<ll> sum(res.size() - );
for (int i = ; i < res.size() - ; i++)
sum[i] = (ll)res[i + ].first - - res[i].second;
sum.push_back(INF);
for (int i = ; i < sum.size(); i++)
sum[i] += sum[i - ];
ll maxn = ;
for (int i = ; i < sum.size(); i++)
{
ll tmp = (i == ? : sum[i - ]);
int pos = upper_bound(sum.begin() + i, sum.end(), m + tmp) - sum.begin();
ll tmp2 = (pos == i ? m : m - (sum[pos - ] - tmp));
maxn = max(maxn, res[pos].second - res[i].first + + tmp2);
}
printf("%lld\n", maxn);
}
return ;
}

最新文章

  1. Hibernatel框架基础使用
  2. Autofac
  3. poj 3621 二分+spfa判负环
  4. [原创] WINDOWS 7 精简教程之驱动精简 可用于64和32
  5. String reorder
  6. Java动手实验及课后程序
  7. 使用 Feedly RSS阅读器订阅技术大牛的博客
  8. 让python输出不自行换行的方法
  9. Java 面向对象(转)
  10. 【leetcode】Candy(python)
  11. pudn下载地址的规律
  12. MAC 相关操作解析
  13. [笔记]《JavaScript高级程序设计》- JavaScript简介
  14. ORA-01940: cannot drop a user that is currently connected解决方法
  15. oracle INS-13001 环境不满足最低要求
  16. Nmap参考指南(Man Page)
  17. Sonar+maven+jenkins集成,Java代码走查
  18. CocosCreator小栗子
  19. 题目1018:统计同成绩学生人数(数组或者map)
  20. git分支流

热门文章

  1. java多线程synchronized volatile解析
  2. hdu 1811拓扑排序+并查集(容器实现)
  3. Linux下汇编语言学习笔记80 ---
  4. 微软消息队列MessageQueue(MQ)
  5. 联想S820 MIUI刷机包 MIUI 4.4.30 流畅执行 在线主题破解
  6. 百度LBS云搜索时报错 &amp;quot;filter:area is not filteable field, please set property in the cloud-storage
  7. 嵌入式C语言经常使用keyword
  8. Codeforces Round #325 (Div. 2) B. Laurenty and Shop 前缀+后缀
  9. 重启标志log
  10. 在PL/SQL使用游标获取数据及动态SQL