本人请你这个巨佬来估一估：），是你们在卡我们的题解
2 个赞
我所指的那题应该是 CF1305F，你可以去看题解里面有错误概率的具体计算。
那我讲的通俗一点：那你有本事卡啊。你卡不掉就不要叫，这么简单的道理不懂吗
1 个赞
不接受别人的 hack，你的眼睛容不下沙子？
题解代码明显不是随机化
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
typedef long long ll;
typedef unsigned un;
ll read()
{
ll 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*10+(c-'0'),c=getchar();
return f*x;
}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
void umin(ll& a,ll t){if(a>t)a=t;}
bool umax(ll& a,ll t){if(a<t)return a=t,1;return 0;}
#define MAXN 200011
ll a[MAXN],b[MAXN];
ll ans=0;
struct Line
{
ll k,b;
Line(ll _k=0,ll _b=0){k=_k,b=_b;}
ll f(int x){return k*x+b;}
};
struct Segment_Tree
{
std::vector<Line>v[MAXN<<2|1];
int it[MAXN<<2|1],len;
#define rtv v[num]
#define rtp it[num]
#define bk2 rtv[rtv.size()-2]
#define bk1 rtv[rtv.size()-1]
void build(ll* arr,un l,un r,un num)
{
rtv.clear();
for(int i=l;i<=r;++i)
{
Line cur(arr[i],-arr[i]*i);
while(rtv.size()>1&&double(bk1.b-bk2.b)*(cur.k-bk1.k)<=double(cur.b-bk1.b)*(bk1.k-bk2.k))rtv.pop_back();
if(rtv.empty()||bk1.k!=cur.k)rtv.push_back(cur);
rtp=0;
}
if(l==r)return;
un mid=(l+r)>>1;
build(arr,l,mid,num<<1),build(arr,mid+1,r,num<<1|1);
}
ll Query(un ql,un qr,int x,un l=1,un r=1,un num=1)
{
if(num==1)r=len;
if(ql<=l&&r<=qr)
{
while(rtp+1<rtv.size()&& (x+1)*(rtv[rtp+1].k-rtv[rtp].k) >=(-rtv[rtp+1].b+rtv[rtp].b))++rtp;
return rtv[rtp].f(x);
}
un mid=(l+r)>>1;ll res=0;
if(ql<=mid)umax(res,Query(ql,qr,x,l,mid,num<<1));
if(qr>mid)umax(res,Query(ql,qr,x,mid+1,r,num<<1|1));
return res;
}
void build(ll* arr,int n){len=n;build(arr,1,len,1);}
}TA,TB,TAB;
ll fa[MAXN],fb[MAXN],fab[MAXN];
void solve(int l,int r)
{
if(l==r){umax(ans,ll(a[l])*b[l]);return;}
un mid=(l+r)>>1,ls=mid-l+1;
fa[ls]=a[mid],fb[ls]=b[mid],fab[ls]=a[mid]*b[mid];
for(int i=mid-1;i>=l;--i)
fa[i-l+1]=min(a[i],fa[i-l+2]),fb[i-l+1]=min(b[i],fb[i-l+2]),
fab[i-l+1]=fa[i-l+1]*fb[i-l+1];
TA.build(fa,ls),TB.build(fb,ls),TAB.build(fab,ls);
ll ra=a[mid+1],rb=b[mid+1];
for(int i=mid+1;i<=r;++i)
{
umin(ra,a[i]),umin(rb,b[i]);
int posa=std::upper_bound(fa+1,fa+ls+1,ra)-fa-1;
int posb=std::upper_bound(fb+1,fb+ls+1,rb)-fb-1;
if(posa>0&&posb>0)umax(ans,TAB.Query(1,min(posa,posb),i-l+2));
++posb;
if(posb<=posa)umax(ans,TA.Query(posb,posa,i-l+2)*rb);
++posa,--posb;
if(posa<=posb)umax(ans,TB.Query(posa,posb,i-l+2)*ra);
++posb;
if(posa<=ls&&posb<=ls)umax(ans,(i-l+1-max(posa,posb)+1)*ra*rb);
}
solve(l,mid),solve(mid+1,r);
}
int main()
{
int n=read();
for(int i=1;i<=n;++i)a[i]=read(),b[i]=read();
solve(1,n);
printf("%lld\n",ans);
return 0;
}
不能卡就不要吵，不要叫，这一点做到有那么难吗？
2 个赞
但是“不通过概率小”之类的言论是你们说的。
看我的上个帖子，里面有一个类似的代码可以卡
有用随机化的题解。
1 个赞
不会证概率就不要吵，不要叫，这一点做到有那么难吗？
+1，你们卡，你们算，你们证，你们却啥都没干
2 个赞
发个txt也行啊
2 个赞
提出所谓TLE概率的是你还要我来证是吗。
那你卡不掉你叫什么？如果很难构造数据使他TLE，他就是对的啊。
况且随机化以后显然数据很随机。
那我让你来证明证明，你的那个hash正确的概率是多少啊
2 个赞
你们可以hack，没有意见，但是我认为在这里吵是没有任何意义的，题解明确说明是线段树维护凸包，只是我们老师也讲了这么一种做法，你们要卡随便，没有意见。
2 个赞
如果很难构造数据使他TLE，他就是对的啊。
你要不看看你在说什么。
咱不就是在讨论在运气极差的情况下可能会T的代码是不是正解
2 个赞
我也不反对卡，但是卡呀
2 个赞
代码不给，上来就一个傻逼/cf
1 个赞
建议管理员让此贴结。