比赛 |
NOIP2023模拟赛4 |
评测结果 |
AAAAAAAAWW |
题目名称 |
雪花 |
最终得分 |
80 |
用户昵称 |
宇战 |
运行时间 |
2.780 s |
代码语言 |
C++ |
内存使用 |
23.66 MiB |
提交时间 |
2023-11-16 08:43:07 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,m,w,h;
long long ans;
const int W=50010,H=110;
struct node{
int x,y;
}a[W*H];
struct nd{
int l,r;long long sum,add;
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define add(x) t[x].add
}t[W*10];
void build(int p,int l,int r){
l(p)=l,r(p)=r;
if(l==r){
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
sum(p)=sum(p*2)+sum(p*2+1);
}
void spread(int p){
if(add(p)){
sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
add(p*2)+=add(p);
add(p*2+1)+=add(p);
add(p)=0;
}
}
void change(int p,int l,int r,int d){
if(l<=l(p)&&r>=r(p)){
sum(p)+=(long long)d*(r(p)-l(p)+1);
add(p)+=d;
return;
}
spread(p);
int mid=(l(p)+r(p))/2;
if(l<=mid)change(p*2,l,r,d);
if(r>mid)change(p*2+1,l,r,d);
sum(p)=sum(p*2)+sum(p*2+1);
}
long long ask(int p,int l,int r){
if(l<=l(p)&&r>=r(p)){
return sum(p);
}
spread(p);
int mid=(l(p)+r(p))/2;
long long val=0;
if(l<=mid)val+=ask(p*2,l,r);
if(r>mid)val+=ask(p*2+1,l,r);
return val;
}
int main(){
freopen("snow.in","r",stdin);
freopen("snow.out","w",stdout);
cin>>w>>h;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
char x;
cin>>x;
if(x=='*'){
a[++n].x=i;
a[n].y=j;
}
}
}
build(1,1,w);
for(int i=1;i<=n;i++){
int l=1,r=w;
if(a[i].x==h){
change(1,a[i].y,a[i].y,1);
continue;
}
if(a[i].y-(h-a[i].x)>0){
l=a[i].y-(h-a[i].x);
}
if(a[i].y+h-a[i].x<=w){
r=a[i].y+h-a[i].x;
}
change(1,l,r,1);
}
for(int i=1;i<=w;i++){
ans=max(ans,ask(1,i,i));
}
cout<<ans;
return 0;
}