这代码……emmm……有耐心帮忙换行的大佬肯定很少吧……
by emming @ 2018-08-04 15:57:46
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct plc
{
long long c,x,y1,y2;
}a[20100];
long long n,w,h,laz[80100],val[80100],k[20100],ans,e;
bool cmp(plc a,plc b)
{
if(a.x==b.x) return a.c>b.c;
else return a.x<b.x;
}
void build(long long root,long long l,long long r)
{
laz[root]=val[root]=0;
if(l==r) return;
long long mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid+1,r);
}
void change(long long root,long long l,long long r,long long xx,long long yy,long long cc)
{
if(r<xx||l>yy) return;
if(l>=xx&&r<=yy)
{
val[root]+=cc;
laz[root]+=cc;
return;
}
long long mid=(l+r)/2;
if(laz[root]!=0)
{
laz[root*2]+=laz[root];
val[root*2]+=laz[root];
laz[root*2+1]+=laz[root];
val[root*2+1]+=laz[root];
laz[root]=0;
}
change(root*2,l,mid,xx,yy,cc);
change(root*2+1,mid+1,r,xx,yy,cc);
val[root]=max(val[root*2],val[root*2+1]);
}
int main()
{
cin>>e;
while(e--)
{
scanf("%lld%lld%lld",&n,&w,&h);
long long n2=2*n;
for(long long i=1;i<=n;i++)
{
long long lx=0,ly=0,lc=0;
scanf("%lld%lld%lld",&lx,&ly,&lc);
a[i].x=lx;
a[i].y1=ly;
a[i].y2=ly+h-1;
a[i].c=lc;
a[i+n].x=lx+w-1;
a[i+n].y1=ly;
a[i+n].y2=ly+h-1;
a[i+n].c=-lc;
k[i]=ly;
k[i+n]=ly+h-1;
}
sort(k+1,k+n2+1);
long long m=unique(k+1,k+n+1)-(k+1);
for(long long i=1;i<=n2;i++)
{
a[i].y1=lower_bound(k+1,k+m+1,a[i].y1)-k;
a[i].y2=lower_bound(k+1,k+m+1,a[i].y2)-k;
}
build(1,1,m);
sort(a+1,a+n2+1,cmp);
for(long long i=1;i<=n2;i++)
{
change(1,1,m,a[i].y1,a[i].y2,a[i].c);
ans=max(ans,val[1]);
}
printf("%lld\n",ans);
ans=0;
}
return 0;
}
by octives @ 2018-08-04 15:58:26
函数分开写
by intel_core @ 2018-08-04 16:14:08