只有代码顺序的更换为何会造成 TLE
查看原帖
只有代码顺序的更换为何会造成 TLE
496840
SAMSHAWCRAFT楼主2022/3/26 16:26

我在写莫队对询问排序的时候,写成下面这样会只有两个数据点 AC,其余数据点全部 TLE。

lim=500;
for(int cx=0,u,v;cx<q;++cx){
  std::cin>>u>>v;
  qs[cx]=query_t{u,v,cx};
}
std::sort(qs,qs+q);
std::fill(md.big,md.big+hspp+1,1);

但是如果把 lim 的计算放在后面,如下:

for(int cx=0,u,v;cx<q;++cx){
  std::cin>>u>>v;
  qs[cx]=query_t{u,v,cx};
}
lim=500;
std::sort(qs,qs+q);
std::fill(md.big,md.big+hspp+1,1);

就只有两个数据点 TLE,其余全部 AC。请问这个是什么原理呢?

另外,我写的这份代码总是 TLE,交了三页还是 78 分,不知道是复杂度假了还是什么地方写错了,我打算写的是 O(nV4+nq+qlogq+qV3logV)O(n\sqrt[4]V + n\sqrt q + q\log q+\frac{q\sqrt[3]V}{\log V}) 复杂度。

全代码见剪贴板

2022/3/26 16:26
加载中...