注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

URAL1105[Observers Coloring]  

2011-11-25 23:38:03|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
离散化+线段树+动规。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-22
DESCRIPTION:
$DESCRIPTION
*/

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

#define end first
#define begin second
#define segment first
#define id second
typedef pair<double,double> segment;
typedef
pair<segment,int> segment_with_id;

int
N;
segment_with_id one[10000+1];
double
t[2][10000+1];
int
rid[10000+1];
int
d2ic;
pair<int,int> d2i[20000+2];
int
tidc;
int
tid[2][10000+1];
double
i2d[20000+2];
double
f[10000+1];
int
pre[10000+1];
int
best_id;
int
st1[(20000+2)*4];
int
st2[(20000+2)*4];
int
answerc;
int
answer[10000+1];

bool
sort_rule(const pair<int,int>& a,const pair<int,int>& b)
{

return
t[a.first][a.second]<t[b.first][b.second];
}

void
insert1(int L,int R,int p,int v,int root=1)
{

if
(L<=p&&p<=R)
{

if
(f[st1[root]]<f[v])
st1[root]=v;
if
(L==R) return;
int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
insert1(LL,LR,p,v,Lroot);
insert1(RL,RR,p,v,Rroot);
}
}

int
query1(int L,int R,int p,int root=1)
{

if
(p<L) return 0;
else if
(R<=p) return st1[root];
else

{

int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
int
a=query1(LL,LR,p,Lroot),b=query1(RL,RR,p,Rroot);
return
f[a]>f[b]?a:b;
}
}

void
insert2(int L,int R,int p,int v,int root=1)
{

if
(L<=p&&p<=R)
{

if
(f[st2[root]]-i2d[tid[1][st2[root]]]*2.0<f[v]-i2d[tid[1][v]]*2.0)
st2[root]=v;
if
(L==R) return;
int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
insert2(LL,LR,p,v,Lroot);
insert2(RL,RR,p,v,Rroot);
}
}

int
query2(int L,int R,int p,int root=1)
{

if
(R<p) return 0;
else if
(p<=L) return st2[root];
else

{

int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
int
a=query2(LL,LR,p,Lroot),b=query2(RL,RR,p,Rroot);
return
f[a]-i2d[tid[1][a]]*2.0>f[b]-i2d[tid[1][b]]*2.0?a:b;
}
}


int
main()
{

cin>>t[0][0]>>t[1][0]
>>
N;
d2i[d2ic++]=make_pair(0,0),
d2i[d2ic++]=make_pair(1,0);
for
(int i=1;i<=N;i++)
{

cin>>one[i].segment.begin>>one[i].segment.end;
one[i].id=i;
}

sort(one+1,one+N+1);
for
(int i=1;i<=N;i++)
{

t[0][i]=one[i].segment.begin,
t[1][i]=one[i].segment.end;
rid[i]=one[i].id;
d2i[d2ic++]=make_pair(0,i),
d2i[d2ic++]=make_pair(1,i);
}

sort(d2i,d2i+d2ic,sort_rule);
for
(int i=0;i<d2ic;i++)
{

if
(i&&t[d2i[i].first][d2i[i].second]!=t[d2i[i-1].first][d2i[i-1].second]) tidc++;
tid[d2i[i].first][d2i[i].second]=tidc;
i2d[tidc]=t[d2i[i].first][d2i[i].second];
}

f[best_id=0]=0;
for
(int i=1;i<=N;i++)
{

int
npre;
double
nf;
npre=0;
nf=i2d[tid[1][i]]-i2d[tid[0][i]];
if
(nf>f[i])
{

pre[i]=npre;
f[i]=nf;
}

npre=query1(0,tidc,tid[0][i]);
nf=i2d[tid[1][i]]-i2d[tid[0][i]]+f[npre];
if
(nf>f[i])
{

pre[i]=npre;
f[i]=nf;
}

npre=query2(0,tidc,tid[0][i]);
nf=f[npre]-i2d[tid[1][npre]]*2.0+i2d[tid[0][i]]+i2d[tid[1][i]];
if
(nf>f[i])
{

pre[i]=npre;
f[i]=nf;
}

if
(f[i]>f[best_id]) best_id=i;
insert1(0,tidc,tid[1][i],i);
insert2(0,tidc,tid[1][i],i);
}

if
(f[best_id]>=(i2d[tid[1][0]]-i2d[tid[0][0]])*2.0/3.0)
{

answer[answerc=1]=best_id;
while
(pre[answer[answerc]])
{

answer[answerc+1]=pre[answer[answerc]];
answerc++;
}

cout<<answerc<<endl;
for
(int i=1;i<=answerc;i++)
cout<<rid[answer[i]]<<endl;
}

else
cout<<0<<endl;
return
0;
}
  评论这张
 
阅读(670)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018