Stars in Your Window

There are several test cases in the input. The first line of each case contains 3 integers: n, W, H, indicating the number of stars, the horizontal length and the vertical height of the rectangle-shaped window. Then n lines follow, with 3 integers each: x, y, c, telling the location (x, y) and the brightness of each star. No two stars are on the same point.

There are at least 1 and at most 10000 stars in the sky. $1 \leq W，H \leq 1000000, 0 \leq x，y<2^{31}.$

C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 2408K, 提交时间: 2020-04-25 21:34:19

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int u=20010;
struct rec{unsigned int x,l,r; int c;}a[u];
struct{int p,l,r,dat,add;}t[u*4];
unsigned int b[u],c[u],x,y,w,h;
int n,m,p,i,ans,z;

bool cmp(rec a,rec b)
{
	return a.x<b.x||a.x==b.x&&a.c<b.c;
}

void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r,t[p].dat=t[p].add=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}

void spread(int p)
{
	if(t[p].add)
	{
		t[p*2].dat+=t[p].add,t[p*2].add+=t[p].add;
		t[p*2+1].dat+=t[p].add,t[p*2+1].add+=t[p].add;
		t[p].add=0;
	}
}

void change(int p,int l,int r,int c)
{
	if(l<=t[p].l&&r>=t[p].r)
	{
		t[p].dat+=c,t[p].add+=c;
		return;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) change(p*2,l,r,c);
	if(r>mid) change(p*2+1,l,r,c);
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}

int main()
{
	while(cin>>n>>w>>h)
	{
		for(m=p=0,i=1;i<=n;i++)
		{
			scanf("%u%u%d",&x,&y,&z);
			a[i].l=a[n+i].l=y,a[i].r=a[n+i].r=y+h-1;
			a[i].x=x,a[n+i].x=x+w,a[i].c=z,a[n+i].c=-z;
			b[++m]=y,b[++m]=y+h-1;
		}
		//离散化 
		sort(b+1,b+m+1);
		for(i=1;i<=m;i++)
			if(i==1||b[i]!=b[i-1]) c[++p]=b[i];
			
		for(n*=2,i=1;i<=n;i++)
		{
			a[i].l=lower_bound(c+1,c+p+1,a[i].l)-c;
			a[i].r=lower_bound(c+1,c+p+1,a[i].r)-c;
		}
		sort(a+1,a+n+1,cmp);
		build(1,1,p);
		for(ans=0,i=1;i<=n;i++)
		{
			change(1,a[i].l,a[i].r,a[i].c);
			ans=max(ans,t[1].dat);
		}
		cout<<ans<<endl;
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 26ms, 内存消耗: 3264K, 提交时间: 2022-08-30 09:42:43

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,tot,cnt,a[N],f[N];
long long ans;
map<int,int>val;
struct xx{
	int l,r;
	long long v,bj;
}w[4*N];
struct pp{
	int x,l,r,v;
}h[N];
bool cmp(pp p,pp q)
{
	return p.x<q.x;
}
void build(int p,int l,int r)
{
	w[p].l=l;
	w[p].r=r;
	w[p].v=w[p].bj=0;
	if(l==r)	return ;
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void down(int p)
{
	if(w[p].bj)
	{
		w[p*2].v+=w[p].bj;
		w[p*2+1].v+=w[p].bj;
		w[p*2].bj+=w[p].bj;
		w[p*2+1].bj+=w[p].bj;
		w[p].bj=0;
	}
}
void change(int p,int ll,int rr,int v)
{
	int l=w[p].l;
	int r=w[p].r;
	if(ll<=l&&r<=rr)
	{
		w[p].v+=v;
		w[p].bj+=v;
		return ;
	}
	down(p);
	int mid=(l+r)/2;
	if(ll<=mid)	change(p*2,ll,rr,v);
	if(mid<rr)	change(p*2+1,ll,rr,v);
	w[p].v=max(w[p*2].v,w[p*2+1].v);
}
long long ask(int p)
{
	return w[p].v;
}
int main()
{
	while(cin>>tot>>n>>m)
	{
		cnt=ans=0;
		for(int i=1;i<=tot;i++)	
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			a[++cnt]=y;
			h[cnt]={x,y,y+m-1,z};
			a[++cnt]=y+m-1;
			h[cnt]={x+n,y,y+m-1,-z};
		}
		sort(a+1,a+cnt+1);
		sort(h+1,h+cnt+1,cmp);
		val.clear();
		int v=0;
		for(int i=1;i<=cnt;i++)
		{
			if(i==1||a[i]!=a[i-1])
			{
				val[a[i]]=++v;
				f[v]=a[i];
			}
		}
		build(1,1,v);
		for(int i=1;i<=cnt;i++)
		{
			change(1,val[h[i].l],val[h[i].r],h[i].v);
			ans=max(ans,ask(1));
		}
		cout<<ans<<endl;
	}
	return 0;
}

C++ 解法, 执行用时: 20ms, 内存消耗: 1660K, 提交时间: 2022-01-14 18:49:37

#include<bits/stdc++.h>
#define lb lower_bound
using namespace std;
long long xs[10000],ys[10000],X[20000],Y[20000];
int cs[10000],nv[80000],nm[80000],n,W,H;
pair<pair<int,int>,pair<int,int> > et[20000];
void ad(int fm,int to,int v,int i,int l,int r){
	if(fm<=l&&r<=to){nv[i]+=v;nm[i]+=v;return;}
	int m=(l+r)/2;
	if(fm<=m)ad(fm,to,v,i*2,l,m);
	if(m<to)ad(fm,to,v,i*2+1,m+1,r);
	nm[i]=max(nm[i*2],nm[i*2+1])+nv[i];
}
int main(){
	while(cin>>n>>W>>H){
		int ans=0;
		for(int i=0;i<n;i++)cin>>xs[i]>>ys[i]>>cs[i],xs[i]*=2,ys[i]*=2;
		for(int i=0;i<n;i++)X[i*2]=xs[i]-W,X[i*2+1]=xs[i]+W,Y[i*2]=ys[i]-H,Y[i*2+1]=ys[i]+H-1;
		sort(X,X+2*n);
		sort(Y,Y+2*n);
		for(int i=0;i<n;i++){
		et[i*2]=make_pair(make_pair(lb(X,X+n*2,xs[i]-W)-X,cs[i]),make_pair(lb(Y,Y+n*2,ys[i]-H)-Y,lb(Y,Y+n*2,ys[i]+H-1)-Y));
		et[i*2+1]=make_pair(make_pair(lb(X,X+n*2,xs[i]+W)-X,-cs[i]),make_pair(lb(Y,Y+n*2,ys[i]-H)-Y,lb(Y,Y+n*2,ys[i]+H-1)-Y));
		}
		sort(et,et+2*n);
		for(int i=0;i<2*n;i++)ad(et[i].second.first,et[i].second.second,et[i].first.second,1,0,2*n),ans=max(ans,nm[1]);
		cout<<ans<<"\n";
	}
	return 0;
}

详情