当前位置：首页 > news >正文

打卡信奥刷题（3225）用C++实现信奥题 P8370 [POI 2001 R3] Goldmine

news 2026/5/7 23:04:49

P8370 [POI 2001 R3] Goldmine

题目描述

Byteman\text{Byteman}Byteman作为Byteland\text{Byteland}Byteland的The Goldmine\text{The Goldmine}The Goldmine（某一公司厂矿）的最有功的雇员之一，即将在年末退休。

为了表示对他的认真勤恳的工作的承认，The Goldmine\text{The Goldmine}The Goldmine的管理层愿意奖励他一小块长方形的矿地，此矿地长和宽为sss和www，且平行于坐标系统的轴线。长方形矿地的位置可由他自己选。当然，这块地的价值会随着位置的不同而不同。其价值是指这块区域内天然金矿石的数量（若矿石位于这块地的边缘，我们同样认为他是属于这个区域的）。

你们的任务是计算出这块地的最大可能价值（即：为它选择最佳位置）。为简便起见，我们假定整个金矿的矿区是无穷的，但含有天然金矿石的区域却是有限的。

请你编写一个程序：

读入天然金矿石的位置。
计算这块地的最大可能价值（即：求给定大小的这块地所含的天然金矿石的最大数）。

输入格式

第一行输入两个正整数s,ws,ws,w，各自代表着此矩形区域平行XXX轴和YYY轴的边的长度。

第二行输入一个正整数nnn，它表示此金矿矿区内天然矿石的数量。接下来的nnn行，每行输入两个用单个空格隔开的整数x,yx,yx,y，它们分别表示了某一天然金矿石的XXX坐标和YYY坐标。

输出格式

输出一个整数，表示此块给定大小的矿地的最高价值。

输入输出样例 #1

输入 #1

1 2 12 0 0 1 1 2 2 3 3 4 5 5 5 4 2 1 4 0 5 5 0 2 3 3 2

输出 #1

说明/提示

对于100%100\%100%的数据：1≤s,w≤10000,1≤n≤15000,−30000≤x,y≤300001 \le s,w \le 10000,1 \le n \le 15000,-30000 \le x,y \le 300001≤s,w≤10000,1≤n≤15000,−30000≤x,y≤30000。

C++实现

#include<bits/stdc++.h>#definelllonglong#definels(x)x<<1#definers(x)x<<1|1#defineN100005usingnamespacestd;structNN{ll x,l,r,w;}q[N];intT,n,W,H,t,cnt;ll ans,a[N],lz[N],tr[N];intcmp(NN a,NN b){returna.x==b.x?a.w>b.w:a.x<b.x;}voidpushup(intx){tr[x]=max(tr[ls(x)],tr[rs(x)]);}voidpushdown(intx){if(lz[x]){tr[ls(x)]+=lz[x],lz[ls(x)]+=lz[x];tr[rs(x)]+=lz[x],lz[rs(x)]+=lz[x],lz[x]=0;}}voidupdate(intx,intl,intr,intL,intR,intw){if(L>R)return;if(l>=L&&r<=R){tr[x]+=w,lz[x]+=w;return;}intmid=(l+r)>>1;if(lz[x])pushdown(x);if(R<=mid)update(ls(x),l,mid,L,R,w);elseif(L>mid)update(rs(x),mid+1,r,L,R,w);elseupdate(ls(x),l,mid,L,mid,w),update(rs(x),mid+1,r,mid+1,R,w);pushup(x);}intmain(){scanf("%d%d%d",&W,&H,&n),W++,H++;for(ll i=1,x,y;i<=n;i++){scanf("%lld%lld",&x,&y);a[++t]=y,a[++t]=y+H-1;q[++cnt]={x,y,y+H-1,1},q[++cnt]={x+W-1,y,y+H-1,-1};}sort(a+1,a+t+1);t=unique(a+1,a+t+1)-(a+1);sort(q+1,q+cnt+1,cmp);for(inti=1;i<=cnt;i++){intl=lower_bound(a+1,a+t+1,q[i].l)-a;intr=lower_bound(a+1,a+t+1,q[i].r)-a;update(1,1,t,l,r,q[i].w);ans=max(ans,tr[1]);}printf("%lld",ans);return0;}