栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 2482 Stars in Your Window

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 2482 Stars in Your Window

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;const int N=40005;long long r[N*12];int n;long long w,h;int tot,cnt;long long mx=0;long long maxl(long long a,long long b){return a>b?a:b;}struct line{long long x,y1,y2,c;}pos[N*6];bool cmp(line a,line b){if(a.x==b.x)return a.c<b.c;return a.x<b.x;}struct sgtr{int l,r;long long dat;long long add;}tr[N*6];void build(int p,int l,int r){tr[p].l=l,tr[p].r=r,tr[p].dat=tr[p].add=0;if(l==r)return;int mid=(l+r)/2;build(p*2,l,mid);build(p*2+1,mid+1,r);}void spread(int p){if(tr[p].l==tr[p].r)return;if(tr[p].add){tr[p*2].dat+=tr[p].add;tr[p*2+1].dat+=tr[p].add;tr[p*2].add+=tr[p].add;tr[p*2+1].add+=tr[p].add;}tr[p].add=0;}void change(int p,int l,int r,long long x){if(l<=tr[p].l&&r>=tr[p].r){tr[p].dat+=x;tr[p].add+=x;return;}spread(p);int mid=(tr[p].l+tr[p].r)/2;if(l<=mid)change(p*2,l,r,x);if(r>mid)change(p*2+1,l,r,x);tr[p].dat=maxl(tr[p*2].dat,tr[p*2+1].dat);}void make(){sort(r+1,r+tot+1);for(int i=1;i<=cnt;i++){//pos[i].x=lower_bound(r+1,r+tot+1,pos[i].x)-r;pos[i].y1=lower_bound(r+1,r+tot+1,pos[i].y1)-r;pos[i].y2=lower_bound(r+1,r+tot+1,pos[i].y2)-r;mx=maxl(mx,maxl(pos[i].y2,pos[i].y1));}sort(pos+1,pos+cnt+1,cmp);}void init(){memset(&tr,0,sizeof tr);memset(&pos,0,sizeof pos);memset(r,0,sizeof r);mx=tot=cnt=0;}int main(){while(scanf("%d%I64d%I64d",&n,&w,&h)!=EOF){init();for(int i=1;i<=n;i++){long long a,b,c;scanf("%I64d%I64d%I64d",&a,&b,&c);pos[++cnt].x=a,pos[cnt].y1=b,pos[cnt].y2=b+h-1,pos[cnt].c=c;pos[++cnt].x=a+w,pos[cnt].y1=b,pos[cnt].y2=b+h-1,pos[cnt].c=-c;r[++tot]=b,r[++tot]=b-1,r[++tot]=b+1,r[++tot]=b+h-1,r[++tot]=b+h,r[++tot]=b+h+1;}make();build(1,1,mx+10);unsigned long long ans=0;for(int i=1;i<=cnt;i++){//cout<<"push "<<pos[i].y1<<" "<<pos[i].y2<<" "<<pos[i].c<<endl;change(1,pos[i].y1,pos[i].y2,pos[i].c);ans=maxl(ans,tr[1].dat);//cout<<ans<<endl;}printf("%I64dn",ans);}}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/365710.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号