求问评测机速率问题

Becoder 的评测机型号为 Intel(R) Core(TM) i9-14900K

编译选项为 g++ source_file.cpp -o exec_file -O2 -lm -DONLINE_JUDGE -mx32 -std=c++xx

Luogu 的评测机型号为 Intel(R) Xeon(R) Platinum 8369HC CPU @ 3.30GHz

编译选项为 gcc -DONLINE_JUDGE -Wall -fno-asm -lm -march=native

理论上 Becoder 的评测机速度应当优于 Luogu

在评测对应 Luogu 这道题时：https://www.luogu.com.cn/problem/P13508

同样时限为 3s，Luogu 能过，Becoder TLE

但如果在原代码最末尾添加如下代码就能通过：

CPP

while(clock()*1.0/CLOCKS_PER_SEC<2.9);

求问两个问题：

1.为什么 Becoder 跑的这道题没有 Luogu 快（绝大部分题目 Becoder 会快很多）？

2.为什么添加那一行代码过后 TLE 的代码就能过了？

原代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=300005,INF=0x3f3f3f3f;
set<int> st;
vector<pair<int,int>> v[N];
int n,d,g,q,a[N],b[N],p[N],t[N],ans[N],far[N];
int to[N],ed[N],lst[N],pre[N],dep[N],mx[555][555];
struct DSU{
    int d[N];
    void init(int n){iota(d,d+n+1,0);}
    void merge(int x,int y){d[find(x)]=find(y);}
    int find(int x){return d[x]==x?x:d[x]=find(d[x]);}
}dsu;
void solve(int l,int r,int cnt=0){
    for(int i=1;i<=n;pre[i++]=cnt)  if(l<=a[i]&&a[i]<=r)  b[++cnt]=i;
    for(int i=1;i<=cnt;i++)
        for(int j=i;j<=cnt;j++)
            mx[i][j]=max(mx[i][j-1],a[b[j]]);
    for(int i=n,p=a[n];i>=1;p=a[--i])  if(p<=r){
        to[p]=max(lst[p],mx[pre[i]+1][pre[far[i]]]);
        if(to[p]<p)  to[p]=0,ed[p]=p,dep[p]=0;
        if(to[p]&&to[p]<l)  ed[p]=ed[to[p]],dep[p]=dep[to[p]]+1;
        if(to[p]&&to[p]>=l)  ed[p]=p,dep[p]=0;
    }
    for(int i=l;i<=r;i++)  for(auto [x,id]:v[i]){
        int pos=1,&res=ans[id];res+=dep[x],x=ed[x];
        for(int mx=lst[x];x<i;mx=lst[x]){
            for(;pos<=cnt&&b[pos]<=far[p[x]];pos++)
                if(b[pos]>p[x]&&a[b[pos]]<=i)  mx=max(mx,a[b[pos]]);
            if(!mx){res=0;break;}x=mx,res++;
        }
    }
    for(int i=1;i<=n;i++)  lst[i]=to[i];
}
int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>d>>g,dsu.init(n);int len=sqrt(n);
    for(int i=1;i<=n;i++)  cin>>a[i],p[a[i]]=i;
    cin>>q,st.insert(INF),st.insert(-INF);
    for(int i=1,x,y;i<=q;i++){
        cin>>t[i]>>x>>y;
        if(a[x]<a[y])  v[a[y]].emplace_back(a[x],i);
    }
    for(int i=1;i<=n;i++){
        st.insert(p[i]);
        auto itl=prev(st.lower_bound(p[i])),itr=st.upper_bound(p[i]);
        if(*itr-d<=p[i])  dsu.merge(p[i],*itr);
        if(*itl+d>=p[i]&&dsu.find(*itl)<=p[i])  dsu.merge(*itl,p[i]);
        far[p[i]]=min(n,dsu.find(p[i])+d);
    }
    for(int l=1,r=len;l<=n;l+=len,r+=len)  solve(l,min(r,n));
    for(int i=1;i<=q;i++)  cout<<(t[i]==1?bool(ans[i]):ans[i])<<"\n";
}

求问评测机速率问题

讨论操作

回复

相关推荐

求问评测机速率问题