跟前面某個題一樣,都是區間染色問題,還是用我的老方法,區間離散化+二分區間端點+區間處理做的,時間跑的還挺短
坑爹的情況就是最左端是0,最右端是1e9,區間求的是開區間
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef struct
{
int l;
int r;
bool color;
}seg;
seg a[5005];
int t[10005];
int d[10005],ct;
int f[10005];
int find(int x,int n)
{
int l=0,r=n-1,mid=(l+r)/2;
while(l<r)
{
if(x>d[mid])l=mid+1;
else r=mid;
mid=(l+r)/2;
}
return mid;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
char e;
scanf("%d %d %c",&t[2*i],&t[2*i+1],&e);
a[i].l=t[2*i];
a[i].r=t[2*i+1];
a[i].color=(e=='w')?0:1;
}
t[2*n]=0;t[2*n+1]=1e9;
sort(t,t+2*n+2);
ct=0;
d[ct++]=t[0];
for(int i=1;i<2*n+2;i++)
if(t[i]!=t[i-1])
d[ct++]=t[i];
memset(f,0,sizeof(f));
for(int i=0;i<n;i++)
{
int L=find(a[i].l,ct);
int R=find(a[i].r,ct);
for(int j=L;j<R;j++)
f[j]=a[i].color;
}
int left=0;
int max=0,a1,a2;
for(int i=0;i<ct;i++)
{
if(f[i]==1||d[i]==1e9)
{
if(left==d[i]){left=d[i+1];continue;}
else {
if(d[i]-left>max){
max=d[i]-left;
a1=left;
a2=d[i];
}
left=d[i+1];
}
}
}
printf("%d %d\n",a1,a2);
return 0;
}