In my code,I have set a limit on the number of iterations but it still Time limit exceeded.
Can anyone tell me how to find the next faster or explain that my code complexity is incorrect.
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
const int M=(int)(2e5),N=(int)(2e5+5);
#define ls ((cur)<<1)
#define rs ((ls)|1)
int n,a[N],mi[N<<2],sum[N],MX,ct0,ct[N];
inline void upt(int x,int v) {
ct[x]+=v;
while(x<=MX) sum[x]+=v,x+=(x&(-x));
}
inline int qry(int x) {
int res=0; while(x) res+=sum[x],x-=(x&(-x)); return res;
}
void push_up(int cur) {
mi[cur]=min(mi[ls],mi[rs]);
}
void upt_add(int cur,int l,int r,int pos,int v) {
if(l==r) {
mi[cur]+=v; upt(l,v);
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) upt_add(ls,l,mid,pos,v);
else upt_add(rs,mid+1,r,pos,v);
push_up(cur);
}
int qry_nex(int cur,int l,int r,int cl,int cr,int v) {
if(mi[cur]>=v) return -1;
if(l==r) return l;
int mid=(l+r)>>1;
if(cl<=l&&r<=cr) {
if(mi[cur]>=v) return -1;
if(mi[rs]<v) return qry_nex(rs,mid+1,r,cl,cr,v);
return qry_nex(ls,l,mid,cl,cr,v);
}
if(cr<=mid) return qry_nex(ls,l,mid,cl,cr,v);
if(cl>mid) return qry_nex(rs,mid+1,r,cl,cr,v);
if(mi[rs]<v) {
int qwq=qry_nex(rs,mid+1,r,cl,cr,v);
if(qwq!=-1) return qwq;
}
return qry_nex(ls,l,mid,cl,cr,v);
}
bool chk(int Lim,int re) {
re*=2;
int nw=Lim-1,tmp=qry(MX)-qry(Lim-1),need=1;
while(nw>=1) {
int pos=qry_nex(1,1,MX,1,nw,need);
// cout<<nw<<" "<<pos<<" "<<need<<" "<<qry_ct(1,0,MX,pos,pos)<<'\n';
if(pos<1) {
tmp+=qry(nw)-nw*need;
break ;
}
int qwq=0;
if(pos<nw) {
// qwq=qry_ct(1,0,MX,pos+1,nw)-(nw-pos)*need;
qwq=qry(nw)-qry(pos);
re-=qwq; tmp+=qwq-(nw-pos)*need;
}
need+=need-(ct[pos]);
if(need>re) {
return 0;
}
nw=pos-1;
}
bool fl=0;
// cout<<qry_ct(1,0,MX,0,0)+tmp<<'\n';
if(ct0+tmp>=need) fl=1;
return fl;
}
void sol() {
cin>>n; MX=n; ct0=0;
for(int i=1;i<=n;i++) cin>>a[i];
int res=1;
for(int i=1;i<=n;i++) {
if(a[i]&&a[i]<=MX) upt_add(1,1,MX,a[i],1);
else ++ct0;
if(i==1) {
cout<<max(1,a[i])<<' ';
continue ;
}
while(chk(res+1,i)) ++res;
cout<<res<<' ';
}
cout<<'\n';
memset(mi,0,sizeof(int)*(4*n+1));
memset(sum,0,sizeof(int)*(n+1));
memset(ct,0,sizeof(int)*(n+1));
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int T; cin>>T; while(T--) sol();
return 0;
}