Source Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<pair<lng,lng>,null_type,less<pair<lng,lng>>,rb_tree_tag,tree_order_statistics_node_update>
#define rtr return 0
#define lng long long
#define endl "\n"
#define cmbntrcs for(int i=1;i<INF;i++){fact[i]=mul(i,fact[i-1]);inv[i]=mod_inv(fact[i]);}
#define nmbrthry
//#pragma GCC optimize
const int MOD=1e9+7,INF=1e6+7,SZ=2e5+7,MSZ=1e5+3;
int add(int x,int y){int z=x+y;if(z>=MOD){z-=MOD;}return z;}
int sub(int x,int y){int z=x-y;if(z<0){z+=MOD;}return z;}
int mul(int x,int y){return(x*1ll*y)%MOD;}
int pwr(int a,lng b)
{
 if(!b){return 1;}
 int res=pwr(a,b/2);res=mul(res,res);if(b%2){res=mul(res,a);}
 return res;
}
int mod_inv(int a){return pwr(a,MOD-2);}
vector<int>fact(INF,1),inv(INF,1);
int nCr(int n,int r){return mul(fact[n],mul(inv[r],inv[n-r]));}
int nPr(int n,vector<int>r)
{
 int den=1;
 for(int i=0;i<r.size();i++){den=mul(den,inv[i]);}
 return mul(fact[n],den);
}
int sb(int s,int b){return nCr(s+b-1,s);}
int prfx(int i,int j){if(i<0||j<0){return 0;}return nCr(i+j,i);}
lng lcm(lng x,lng y){return(x*y/__gcd(x,y));}
lng trig(lng x){return x*(x+1)/2;}
lng sigma(lng x,lng y){return trig(y)-trig(x-1);}
lng fp(lng a,lng b)
{
 if(!b){return 1;}
 lng res=fp(a,b/2);res*=res;if(b%2){res*=a;}
 return res;
}
string num_bin(lng n){if(n==0){return"0";}string x="";while(n){char c=(n%2)+'0';x+=c;n/=2;}reverse(x.begin(),x.end());return x;}
lng bin_num(string x){reverse(x.begin(),x.end());lng n=0;for(int i=0;i<x.size();i++){if(x[i]=='1'){n+=pow(2,i);}}return n;}
struct mtrx
{
 lng nx,mx;vector<vector<lng>>bd;
 void bld(vector<vector<lng>>obd){nx=obd.size(),mx=obd[0].size();bd=obd;}
 void outm(){for(lng i=0;i<nx;i++){for(lng j=0;j<mx;j++){cout << bd[i][j] << ' ';}cout << endl;}}
};
mtrx idnt(lng n)
{
 vector<vector<lng>>v;v.resize(n);
 for(lng i=0;i<n;i++){v[i].assign(n,0);v[i][i]=1;}
 return{n,n,v};
}
mtrx modn(mtrx a,lng x)
{
 for(lng i=0;i<a.nx;i++){for(lng j=0;j<a.mx;j++){a.bd[i][j]%=x;}}
 return a;
}
mtrx mulm(mtrx a,mtrx b)
{
 if(a.mx!=b.nx){return{1,1,{{0}}};}
 vector<vector<lng>>v;v.resize(a.nx);
 for(lng i=0;i<a.nx;i++)
 {
  v[i].resize(b.mx);
  for(lng j=0;j<b.mx;j++)
  {
   lng s=0;
   for(lng x=0;x<a.mx;x++)
   {
    s+=a.bd[i][x]*b.bd[x][j];
    s%=MOD;
   }
   v[i][j]=s;
  }
 }
 mtrx ret;ret.bld(v);
 //MOD FACTOR ret=modn(ret,MOD);
 return ret;
}
mtrx fpm(mtrx a,lng b)
{
 if(b==0){return idnt(a.nx);}
 mtrx ret=fpm(a,b/2);ret=mulm(ret,ret);
 if(b%2){ret=mulm(ret,a);}
 return ret;
}
lng rndm(lng a,lng b){return a+rand()%((b+1)-a);}
lng rnd_num(lng n)
{lng z=rndm(1,9);n--;while(n--){z*=10;z+=rndm(0,9);}return z;}
lng n,q,a[MSZ],sprs[32][MSZ],prf[MSZ];
void blds()
{
 for(lng i=0;i<n;i++){sprs[0][i]=a[i];}
 for(lng j=1;j<32;j++)
 {
  lng xo=(1ll<<(j-1));
  for(lng i=0;i<n;i++)
  {
   if(i+xo+xo>n){break;}
   sprs[j][i]=sprs[j-1][i]|sprs[j-1][i+xo];
  }
 }
 return;
}
lng qry(lng l,lng r)
{
 lng mx=0;string s=num_bin(r+1-l);reverse(s.begin(),s.end());
 for(lng i=0;i<s.size();i++)
 {
  if(s[i]=='0'){continue;}
  mx|=sprs[i][l];
  l+=(1ll<<i);
 }
 return mx;
}
int main()
{
 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 lng tt;cin >> tt;
 while(tt--)
 {
  lng n;cin >> n;lng a[n],ad[n],sb[n],admx[n];
  for(lng i=0;i<n;i++){cin >> a[i];ad[i]=a[i]+i+1;sb[i]=(i+1)-a[i];}
  admx[0]=ad[0];for(lng i=1;i<n;i++){admx[i]=max(admx[i-1],ad[i]);}
  for(lng i=0;i<n;i++)
  {
   lng l=0,r=n-1,ans=-1;
   while(l<=r)
   {
    lng m=(l+r)/2;
    if(sb[i]<=admx[m]){r=m-1;ans=m;}
    else{l=m+1;}
   }
   if(ans==-1){cout << "-1\n";continue;}
   cout << ans+1 << ' ';
  }
  cout << endl;
 }
 return 0;
}
Copy
Easy challenge? Yahia_Emara
GNU G++17
33 ms
8.2 MB
Wrong Answer