Source Code
#include<bits/stdc++.h>
#include <unordered_map>
#include<unordered_set>
// Header files, namespaces,
// macros as defined above
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
#define _USE_MATH_DEFINES
# define M_PI           3.14159265358979323846  /* pi */
#define ll long long
#define ull unsigned long long
#define ld long double
#define vbe(v) ((v).begin()), ((v).end())
#define sz(v)     ((int)((v).size()))
#define prec(x)    cout<< fixed<< setprecision(x)
#define clr(v, d)   memset(v, d, sizeof(v))
#define rep(i, v)   for(int i=0;i<sz(v);++i)
#define lp(i, n)    for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n)  for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n)  for(int i=(j);i>=(int)(n);--i)
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cin.tie(0);
#define INFLL 1e18
#define INF 1e9
#define MOD 1000000007
#define MOD1 998244353
#define MAXN 200010
#define EPS 1e-6

ll GCD(ll a, ll b) { return (a) ? GCD(b % a, a) : b; }

ll LCM(ll a, ll b) { return a * b / GCD(a, b); }

ll fastpow(ll b, ll p) {
    if (!p) return 1;
    ll ret = fastpow(b, p >> 1);
    ret *= ret;
    if (p & 1) ret *= b;
    return ret;
}

struct segTree {
    int size;
    vector<ll> vals;

    void init(int s) {
        size = 1;
        while (size < s) size *= 2;
        vals.resize(2 * size, 0LL);
    }

    void set(int i, ll v, int node, int lx, int rx) {
        if (rx - lx == 1) {
            vals[node] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m)
            set(i, v, 2 * node + 1, lx, m);
        else
            set(i, v, 2 * node + 2, m, rx);
        vals[node] = vals[2 * node + 1] + vals[2 * node + 2];
    }

    void set(int i, ll v) {
        set(i, v, 0, 0, size);
    }

    ll sum(int l, int r, int node, int lx, int rx) {
        if (lx >= r || l >= rx)return 0;
        if (lx >= l && rx <= r)return vals[node];
        int m = (lx + rx) / 2;
        return sum(l, r, 2 * node + 1, lx, m) + sum(l, r, 2 * node + 2, m, rx);
    }

    ll sum(int l, int r) {
        return sum(l, r, 0, 0, size);
    }
};

void solve(int tst) {
    //for each i find mn idx j .. i - ai <= j+aj
    int n;
    cin >> n;
    vector<ll> vec(n);
    lp(i, n)cin >> vec[i];
    set<pair<ll, ll>> tmp;
    ll prev=-INFLL;
    lp(i, n) {
        ll tt=vec[i]+i;
        if(tt>prev){
            prev=tt;
            tmp.insert({tt,i});
        }
    }

    lp(i, n) {
        pair<int,int>toFind={i - vec[i],0};
        auto tt=tmp.lower_bound(toFind);
        if (tt == tmp.end())cout << -1;
        else cout << tt->second + 1;
        cout << " ";
    }
}

int main() {
    FASTIO;
    //freopen("circles.in", "r", stdin);
    int t = 1;
    cin >> t;
    lp(i, t) {
        solve(i + 1);
        cout << "\n";
    }
}
Copy
Easy challenge? gaserashraf
GNU G++17
168 ms
15.7 MB
Accepted