比赛 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;

}