发现这种合并区间的题目还可以这么玩
给你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 ;
}