BZOJ4925 城市规划

　　对每个人行道求出移动距离在哪些区间内时其在建筑物前面。现在问题即为选一个点使得其被最多的区间包含。差分即可。对建筑暴力去掉重叠部分。开始时没有去重用了nm次vector的push_back，时间大概是去重写法的300倍，不知所措。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define N 10010

#define M 1010

#define K 1000010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,a[N],delta[K<<],cnt,d=K,s;

struct data

{

    int l,r;

    bool operator <(const data&a) const

    {

        return l<a.l;

    }

}b[M],c[M];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4925.in","r",stdin);

    freopen("bzoj4925.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++) a[i]=read();

    for (int i=;i<=m;i++) b[i].l=read(),b[i].r=read();

    for (int i=;i<=m;i++)

    {

        bool flag=;

        for (int j=;j<=m;j++)

        if (i!=j&&b[j].l<=b[i].l&&b[j].r>=b[i].r) {flag=;break;}

        if (flag) c[++cnt]=b[i];

    }

    m=cnt;sort(c+,c+m+);

    cnt=;

    for (int i=;i<=m;i++)

    {

        int t=i;

        while (t<m&&c[t+].l<=c[t].r) t++;

        cnt++;b[cnt].l=c[i].l,b[cnt].r=c[t].r;

        i=t;

    }

    m=cnt;

    for (int i=;i<=n;i++)

        for (int j=;j<=m;j++)

        delta[b[j].l-a[i]+K]++,delta[b[j].r+-a[i]+K]--;

    cnt=;

    for (int i=;i<(K<<);i++)

    {

        cnt+=delta[i];

        if (cnt>s||cnt==s&&abs(i-K)<d) d=abs(i-K),s=cnt;

    }

    cout<<d<<' '<<s;

    return ;

}