对每个人行道求出移动距离在哪些区间内时其在建筑物前面。现在问题即为选一个点使得其被最多的区间包含。差分即可。对建筑暴力去掉重叠部分。开始时没有去重用了nm次vector的push_back,时间大概是去重写法的300倍,不知所措。
#include#include #include #include #include #include #include using namespace std;#define ll long long#define N 10010#define M 1010#define K 1000010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,a[N],delta[K<<1],cnt,d=K,s;struct data{ int l,r; bool operator <(const data&a) const { return l =b[i].r) {flag=0;break;} if (flag) c[++cnt]=b[i]; } m=cnt;sort(c+1,c+m+1); cnt=0; for (int i=1;i<=m;i++) { int t=i; while (t <=c[t].r) t++; cnt++;b[cnt].l=c[i].l,b[cnt].r=c[t].r; i=t; } m=cnt; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) delta[b[j].l-a[i]+K]++,delta[b[j].r+1-a[i]+K]--; cnt=0; for (int i=0;i<(K<<1);i++) { cnt+=delta[i]; if (cnt>s||cnt==s&&abs(i-K)