发现这种合并区间的题目还可以这么玩

给你n段时间 然后问没被占用的时间是多少

题目所给的区间是右开的导致我wa

好多人5e5*1440的暴力跑出来的时间居然只是我的两倍 不懂....

所以并查集并没有跑的很快  奇怪....

 #include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <limits.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5+;
int par[maxn];
int l[maxn],r[maxn];
bool vis[maxn];
void init(int n_)
{
for(int i=;i<=n_;i++)
{
par[i] = i;
l[i] = r[i] = i;
}
memset(vis,false,sizeof(vis));
}
int find(int x)
{
if(x!=par[x])
{
return par[x] = find(par[x]);
}
return x;
}
void unite(int x,int y)
{
x = find(x);
y = find(y);
if(x==y) return ;
par[x] = y;
l[y] = min(l[y],l[x]);
r[y] = max(r[y],r[x]); return ;
}
void make(int x,int y)
{
int pre = x;
for(int i=x;i<y;i==r[find(i)]?i++:i=r[find(i)])
{
//cout<<i<<r[i]<<endl;
if(vis[i])
{
pre = i;
continue;
}
vis[i] = true;
unite(pre,x);
pre = i;
}
}
int main()
{
int n;
int lim = *;
while(scanf("%d",&n)!=EOF)
{
init(lim);
int L = ,R = ,a,b,c,d;
for(int i=;i<n;i++)
{
scanf("%d:%d %d:%d",&a,&b,&c,&d);
L = a*+b;
R = c*+d;
make(L,R); }
int ans = ;
for(int i=;i<lim;i++)
{
if(false==vis[i]) ans++;
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. php 实现设计模式之 建造者模式
  2. HashSet
  3. Struts2:MyEclippse中使用struts-default.xml中定义的拦截器(timmer,logger)
  4. 通过System.getProperties()获取系统参数
  5. NHibernate one-to-one
  6. UWP深入学习二:各种激活方式
  7. 使用Thread类可以创建和控制线程
  8. Nginx与X-Sendfile
  9. IO(Input&amp;Output)流の介绍
  10. 【一天一道LeetCode】#14 Longest Common Prefix
  11. mysql varcahr转int类型
  12. SQL中IN与EXISTS的区别
  13. MapServer Tutorial——MapServer7.2.1教程学习——第一节用例实践:Example1.6 Defining Projections and Extents
  14. Mybatis面试题
  15. HDU - 3974 Assign the task (线段树区间修改+构建模型)
  16. Android 利用二次贝塞尔曲线模仿购物车加入物品抛物线动画
  17. 那些年的 网络通信之 TCP/IP 传输控制协议 ip 加 端口 ---
  18. composer安装与应用
  19. Jenkins关联GitHub进行构建
  20. const在c和c++中地位不同

热门文章

  1. ShutdownHook作用
  2. DOM学习笔记(一)DOM树
  3. Qt开篇
  4. Unity动画事件
  5. OPENGL4_变换
  6. swipe轮播插件零基础实用
  7. SLAM学习资料整理(转)
  8. 用css固定textarea文本域大小尺寸
  9. centos 7 安装node.js
  10. scrapy框架中Download Middleware用法