- 圆和点
- 2016-11-15 20:34:57 @
A三个WA三个QAQ蒟蒻一枚
```
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define dou(x) (x*x)
using namespace std;
const int maxm=30005;
const int maxn=1e3+5;
int n,m,k,tot,maxx,maxt,tt;
struct node{
int l,r,z,la;
}tree1[maxm*4],tree[maxm*4];
struct node1{
int h,l,r,z;
}cir[maxn];
bool cmp(node1 a,node1 b)
{
return a.z<b.z;
}
void pushdown(int z)
{
if(tree[z].la)
{
tree[l(z)].z+=tree[z].la;tree[l(z)].la+=tree[z].la;
tree[r(z)].z+=tree[z].la;tree[r(z)].la+=tree[z].la;
tree[z].la=0;
}
}
void build(int l,int r,int u)
{
tree[u].l=l;tree[u].r=r;
tree1[u].l=l;tree1[u].r=r;
tot=max(tot,u);
if(l==r)
{
return ;
}
int mid=(l+r)>>1;
build(l,mid,l(u));
build(mid+1,r,r(u));
}
void update(int l,int r,int z,int v)
{
if(tree[z].l==l&&tree[z].r==r)
{
tree[z].z+=v;tree[z].la+=v;
return ;
}
pushdown(z);
int mid=(tree[z].l+tree[z].r)>>1;
if(mid>=r)update(l,r,l(z),v);
else if(mid<l)update(l,r,r(z),v);
else{
update(l,mid,l(z),v);
update(mid+1,r,r(z),v);
}
tree[z].z=max(tree[l(z)].z,tree[r(z)].z);
}
int query(int l,int r,int z)
{
if(tree[z].l==l&&tree[z].r==r)
return tree[z].z;
pushdown(z);
int mid=(tree[z].l+tree[z].r)>>1;
if(mid>=r)return query(l,r,l(z));
else if(mid<l) return query(l,r,r(z));
else return max(query(l,mid,l(z)),query(mid+1,r,r(z)));
}
void query(int l,int r,int z,int v)
{
if(z>tot)return;
if(l==r&&tree[z].z==v)
{
tt++;return;
}
pushdown(z);
int mid=(l+r)>>1;
query(l,mid,l(z),v);
query(mid+1,r,r(z),v);
}
int main()
{
freopen("txt.in","r",stdin);
cin>>m>>n>>k;
for(int i=1;i<=k;i++)
scanf("%d%d%d%d",&cir[i].h,&cir[i].l,&cir[i].r,&cir[i].z);
//sort(cir+1,cir+k+1,cmp);
build(1,m,1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
if(abs(cir[j].h-i)>cir[j].r)
continue;
double mx=0;
//if(abs(cir[j].h-i)>0)
mx=sqrt(dou(cir[j].r)-dou(abs(cir[j].h-i)));
//else mx=cir[j].r;//可去除
int mm=floor(mx);
int l=cir[j].l-mm>0?cir[j].l-mm:1;
int r=cir[j].l+mm<=m?cir[j].l+mm:m;
update(l,r,1,cir[j].z);
}
tt=0;
int ans=query(1,m,1);
query(1,m,1,ans);
if(ans==maxx)maxt+=tt;
else if(ans>maxx)maxx=ans,maxt=tt;
for(int j=1;j<=tot;j++)
tree[j]=tree1[j];
}
printf("%d\n%d",maxx,maxt);
return 0;
}
```
到底哪里错了呢QAQ