题解

难得啊,本来能 \(AC\) 的一道题,注释没删,挂了五分,难受

此题暴力很好想,就是直接 \(n^2\) 枚举不同的矩阵组合,记录块内答案和跨块的答案

出题人不会告诉你,这题只要输出块内答案就可以拿到 \(65pts\) 。

一个很简单的优化就是按 \(x_1\) 的值先排个序,然后判断

if (mat[j].x1-mat[i].x2>1) break;

但是这种玄学优化仍可以被上下一条链似的块卡掉,但良心出题人竟然没卡。

正解应该是按两维的坐标均排个序,然后二分查找,求出符合要求的块,复杂度 \(\mathcal O(nlogn)\)

我不会告诉你其实常数小的暴力其实比正解还快了一倍

Code

\(AC\kern 0.4em CODE:\)

#include<bits/stdc++.h>
#define ri register int
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
inline int read() {
ri x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x*f;
}
}
using IO::read;
namespace nanfeng{
#define int long long
#define cmax(x,y) ((x)>(y)?(x):(y))
#define cmin(x,y) ((x)>(y)?(y):(x))
#define FI FILE *IN
#define FO FILE *OUT
#undef bool
static const int N=1e5+7;
struct Matrix{
int x1,y1,x2,y2;
friend inline bool operator<(Matrix m1,Matrix m2) {return m1.x1<m2.x1;}
Matrix(){}
Matrix(int x1,int y1,int x2,int y2):x1(x1),y1(y1),x2(x2),y2(y2){}
}mat[N];
int n,ans;
inline int calc(Matrix m) {
int res=0;
int x=m.x2-m.x1,y=m.y2-m.y1;
if (x>y) swap(x,y);
res+=(x*x<<1);
res+=(y-x)*(x<<1);
return res;
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
n=read();
for (ri i(1);i<=n;p(i)) {
int x1=read(),y1=read(),x2=read(),y2=read();
mat[i]=Matrix(x1,y1,x2,y2);
}
if (n==1) {printf("%lld\n",calc(mat[1]));return 0;}
sort(mat+1,mat+n+1);
// for (ri i(1);i<=n;p(i))
for (ri i(1);i<n;p(i)) {
ans+=calc(mat[i]);
// printf("%lld %lld %lld %lld\n",mat[i].x1,mat[i].y1,mat[i].x2,mat[i].y2);
for (ri j(i+1);j<=n;p(j)) {
if (mat[j].x1-mat[i].x2>1) break;
if (mat[j].x1-mat[i].x2==1) {
if (mat[j].y1-mat[i].y2>1||mat[i].y1-mat[j].y2>1) continue;
if (mat[j].y1-mat[i].y2==1||mat[i].y1-mat[j].y2==1) {ans+=1;continue;}
ans+=(cmin(mat[i].y2,mat[j].y2)-cmax(mat[i].y1,mat[j].y1))<<1;
if (cmax(mat[i].y2,mat[j].y2)>cmin(mat[i].y2,mat[j].y2)) ans+=1;
if (cmax(mat[i].y1,mat[j].y1)>cmin(mat[i].y1,mat[j].y1)) ans+=1;
} else if (mat[j].y1>mat[i].y2) {
if (mat[j].y1-mat[i].y2>1) continue;
ans+=(cmin(mat[i].x2,mat[j].x2)-mat[j].x1)<<1;
if (mat[i].x1<mat[j].x1) ans+=1;
if (cmax(mat[i].x2,mat[j].x2)>cmin(mat[i].x2,mat[j].x2)) ans+=1;
} else {
if (mat[i].y1-mat[j].y2>1) continue;
ans+=(cmin(mat[i].x2,mat[j].x2)-mat[j].x1)<<1;
if (mat[i].x1<mat[j].x1) ans+=1;
if (cmax(mat[i].x2,mat[j].x2)>cmin(mat[i].x2,mat[j].x2)) ans+=1;
}
// if (i==2) printf("%lld %lld %lld %lld ans=%lld\n",mat[j].x1,mat[j].y1,mat[j].x2,mat[j].y2,ans);
}
// printf("ans=%lld\n",ans);
}
// printf("%lld %lld %lld %lld\n",mat[n].x1,mat[n].y1,mat[n].x2,mat[n].y2);
printf("%lld\n",ans+calc(mat[n]));
return 0;
}
#undef int
}
int main() {return nanfeng::main();}

最新文章

  1. EntityFramework 如何进行异步化(关键词:async&#183;await&#183;SaveChangesAsync&#183;ToListAsync)
  2. Mongo DB 2.6 需要知道的一些自身限定
  3. HTML &lt;a&gt; download 属性,点击链接来下载图片
  4. 基于DevExpress开发的GridView如何实现一列显示不同的控件类型
  5. Linux使用本地iso作为yum源
  6. 高性能爬虫为什么使用定制DNS客户端?
  7. cocosBuilder使用总结
  8. Windows Phone开发(6):处理屏幕方向的改变
  9. python 数据清洗之字符串处理
  10. java个内部类的总结
  11. Sql Server免域,异地备份
  12. [转载]用纯css改变下拉列表select框的默认样式
  13. learning scala read from file
  14. 牛客网-《剑指offer》-调整数组顺序使奇数位于偶数前面
  15. Python 爬虫-正则表达式(补)
  16. QWidget切换
  17. hdu2121-Ice_cream’s world II
  18. Eclipse中安装Tomcat
  19. [BZOJ4304]/[JZOJ3486]道路改建
  20. python-ASCII与Unicode

热门文章

  1. Docker部署Mysq集群
  2. 个人博客开发之blog-api项目统一结果集api封装
  3. git时 Failed to connect to 127.0.0.1 port 1080: Connection refused
  4. CentOS 8 已经不再支持,Rocky Linux 才是未来
  5. 【分布式】CAP理论及其应用
  6. 「CF568C」 New Language
  7. 「BZOJ 2956」模积和
  8. python twain
  9. PAT甲级:1064 Complete Binary Search Tree (30分)
  10. Innodb 锁的介绍