Orz IPIP2005 大佬太强了。

3ms

14ms

2ms

41ms
42ms
40ms

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

typedef struct
{
    int x;
    int y;
    int r;
    int w;
}cir;

int n,m;
cir c[1000];
int ans=0;
int maxw=0;
int ll[30001];
int rr[30001];

int abs(int x)
{
    if(x<0)
    {
        return -x;
    }
    else
    {
        return x;
    }
}

int main()
{
    int i,j,k;
    int l,r,d;
    int a;
    cin>>m>>n>>k;
    ans=n*m;
    for(i=0;i<k;i++)
    {
        cin>>c[i].x>>c[i].y>>c[i].r>>c[i].w;
    }
    for(i=1;i<=n;i++)
    {
        memset(ll,0,sizeof(ll));
        memset(rr,0,sizeof(rr));
        for(j=0;j<k;j++)
        {
            if(abs(i-c[j].x)<=c[j].r)
            {
                d=sqrt(c[j].r*c[j].r-(i-c[j].x)*(i-c[j].x));
                l=c[j].y-d;
                r=c[j].y+d;
                l=max(1,l);
                r=min(m,r);
                ll[l]+=c[j].w;
                rr[r]+=c[j].w;
            }
        }
        a=0;
        for(j=1;j<=m;j++)
        {
            a+=ll[j];
            if(a>maxw)
            {
                ans=1;
                maxw=a;
            }
            else if(a==maxw)
            {
                ans++;
            }
            a-=rr[j];
        }
    }
    cout<<maxw<<endl<<ans<<endl;
    return 0;
}

根据一道线段树题目想到O(NM)的

把K个圆在每一行的截区间求出来，(c,d),在c处放b[i]左括号，d处放b[i]个右括号，

即求L[i]-R[i]的最大值，每一行O(M)枚举，总复杂度O(NM);

只是想到了怕忘记,一定赶上做

├ 测试数据 04：答案正确... 338ms

├ 测试数据 05：答案正确... 384ms

├ 测试数据 06：答案正确... 322ms

A掉了,MN是有点慢,有N^2的就可以秒杀了

PS:只处理左边一格有右括号的点,复杂度是O(nk)

测试数据 #0: Accepted, time = 0 ms, mem = 756 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 752 KiB, score = 15
测试数据 #2: Accepted, time = 0 ms, mem = 756 KiB, score = 15
测试数据 #3: Accepted, time = 125 ms, mem = 756 KiB, score = 20
测试数据 #4: Accepted, time = 125 ms, mem = 756 KiB, score = 20
测试数据 #5: Accepted, time = 62 ms, mem = 756 KiB, score = 20

那个算法好像是O(nklogk)的。。因为要排序。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 134ms

├ 测试数据 05：答案正确... 666ms

├ 测试数据 06：答案正确... 259ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1059ms

扫描法 Orz

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 1916ms

├ 测试数据 05：答案正确... 1447ms

├ 测试数据 06：答案正确... 869ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4232ms

好慢!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 1166ms

├ 测试数据 05：答案正确... 1072ms

├ 测试数据 06：答案正确... 900ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3138ms

用O（2NM+NLogM）

Orz gnaggnoyil 神牛，线段树算法太神了！

这个题可以枚举每一个横条

并求出该横条与每个圆的交点横坐标s和t

开一个数组，把该圆的权值加到a中，

并从a[t+1]中减去该圆的权值

然后扫一遍就行了

orz curimit神牛

原来还有O(NK)的方法呀

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 41ms

├ 测试数据 05：答案正确... 41ms

├ 测试数据 06：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：82ms

奇怪，O(NK)怎么秒不掉呢？

Accepted 有效得分：100 有效耗时：2856ms

事实证明ipip2005大牛的方法的确很好，线段树复杂度是O(NMlgM)的，而这个方法只是O(NM)的。

Accepted 有效得分：100 有效耗时：4489ms

我的速度怎么这么慢啊？

正如楼上大牛们所说的：一行一行处理，但是会超时，需要用到线段树。

为了防止这题内存爆掉，最好一行一行地做．每次用k个圆来更新这行．然后一行行地处理．

千万别学我这样，开个a,b:array［１．．１０００，１．．３００００］of longint;的数组．

按IPIP2005大牛的方法,这题用不着高级数据结构

线段树只开30000长的区间

又不是二维线段树,显然能开出来

...

对n离散化,对n个长m的长条做线段树来计算多次对某个区间添加bi后最大值和最大值数.

事实证明，模拟只能40分

弱弱地问..

可不可以模拟..

300亿..