首页 > 代码库 > 【扫描线】Gym - 101190E - Expect to Wait
【扫描线】Gym - 101190E - Expect to Wait
假设初始人数为0,
将每个时刻在等待的人数写下来,就是求个和。
如果纵坐标看成人数,横坐标看成时间,就是求个面积。
因为初始人数不一定为零,所以离线后扫描线即可回答所有询问。
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; int n,m,e; struct LINE{ int y,l,id; }ls[200010]; bool cmp(const LINE &a,const LINE &b){ return a.y!=b.y ? a.y>b.y : a.l<b.l; } ll anss[100010]; int main(){ freopen("expect.in","r",stdin); freopen("expect.out","w",stdout); int x,y; char op[4]; scanf("%d%d",&n,&m); int now=0,last=1; for(int i=1;i<=n;++i){ scanf("%s%d%d",op,&x,&y); if(now>0 && i>1){ ls[++e]=(LINE){now,x-last}; } if(op[0]==‘+‘){ now-=y; } else{ now+=y; } last=x; } if(now>0){ ls[++e]=(LINE){now,1000000001}; } for(int i=1;i<=m;++i){ ++e; scanf("%d",&ls[e].y); ls[e].id=i; ls[e].l=0; } sort(ls+1,ls+e+1,cmp); ll nowans=0; int nowl=0; int i=1; for(;i<=e;++i){ if(ls[i].l==0){ anss[ls[i].id]=nowans; } if(ls[i].y>0 && ls[i].l==1000000001){ break; } nowl+=(ll)ls[i].l; if(ls[i].y!=ls[i+1].y){ nowans+=(ll)(ls[i].y-ls[i+1].y)*(ll)nowl; } } for(;i<=e;++i)if(ls[i].l==0){ anss[ls[i].id]=-1; } for(i=1;i<=m;++i){ if(anss[i]==-1){ puts("INFINITY"); } else{ printf("%I64d\n",anss[i]); } } return 0; }
【扫描线】Gym - 101190E - Expect to Wait
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。