# HackerEarth The maximum distance problem solution

In this HackerEarth The maximum distance problem solution You are given an array a1, a2, ..., aN consisting of N elements. You are given Q queries. Each query is of the following types:
1. The format of the first type of query is 1 L R x. You must increase the values of all elements in range L to R (both inclusive) by integer x.
2. The format of the second type of query is 2 L R y. You must multiply the values of all elements in the range L to R (both inclusive) by the integer y.
3. The format of the third type of query is 3 z. You are required to find the maximum distance between elements that are equal to z in the array. If the element is not present in the array, print -1.

## HackerEarth The maximum distance problem solution.

`#include <bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned long long#define f(a, b) for (ll i = a; i < b; i++)#define mod 1000000007#define pb push_back#define vll vector<ll>#define pll vector<pair<ll, ll>>#define ld long double#define fr(a, b) for (ll j = a; j >= b; j--)#define fi(a, b) for (ll j = a; j < b; j++)#define fii(a, b) for (ll k = a; k < b; k++)template <class T>ostream &operator<<(ostream &os, vector<T> V){    os << "[ ";    for (auto v : V)        os << v << " ";    os << "]";    return os;}template <class T>ostream &operator<<(ostream &os, multiset<T> S){    os << "{ ";    for (auto s : S)        os << s << " ";    return os << "}";}template <class L, class R>ostream &operator<<(ostream &os, pair<L, R> P){    return os << "(" << P.first << "," << P.second << ")";}template <class L, class R>ostream &operator<<(ostream &os, map<L, R> M){    os << "{ ";    for (auto m : M)        os << "(" << m.first << ":" << m.second << ") ";    return os << "}";}ll n, blockSize, a[100005], add[350], mul[350];multiset<pair<ll, ll>> s[350];int main(){#ifndef ONLINE_JUDGE    freopen("input.txt", "rt", stdin);    freopen("output.txt", "wt", stdout);#endif    ios_base::sync_with_stdio(false);    cin.tie(NULL);    cin >> n;    blockSize = sqrt(n);    f(0, n) cin >> a[i], s[i / blockSize].insert({a[i], i});    f(0, 350) mul[i] = 1;    ll q;    cin >> q;    while (q--)    {        ll c;        cin >> c;        if (c == 1 || c == 2)        {            ll l, r, x;            cin >> l >> r >> x;            if (l > r)                swap(l, r);            l--, r--;            ll lBlock = l / blockSize, rBlock = r / blockSize;            if (lBlock == rBlock)            {                f(l, n)                {                    if (i / blockSize != lBlock)                        break;                    s[i / blockSize].erase(s[i / blockSize].find({a[i], i}));                    a[i] *= mul[i / blockSize], a[i] += add[i / blockSize];                    s[i / blockSize].insert({a[i], i});                }                fr(l - 1, 0)                {                    if (j / blockSize != lBlock)                        break;                    s[j / blockSize].erase(s[j / blockSize].find({a[j], j}));                    a[j] *= mul[j / blockSize], a[j] += add[j / blockSize];                    s[j / blockSize].insert({a[j], j});                }                add[lBlock] = 0, mul[lBlock] = 1;                f(l, r + 1)                {                    if (c == 1)                        s[lBlock].erase(s[lBlock].find({a[i], i})), a[i] += x, s[lBlock].insert({a[i], i});                    else                        s[lBlock].erase(s[lBlock].find({a[i], i})), a[i] *= x, s[lBlock].insert({a[i], i});                }            }            else            {                f(l, n)                {                    if (i / blockSize != lBlock)                        break;                    s[i / blockSize].erase(s[i / blockSize].find({a[i], i}));                    a[i] *= mul[i / blockSize], a[i] += add[i / blockSize];                    if (c == 1)                        a[i] += x;                    else                        a[i] *= x;                    s[i / blockSize].insert({a[i], i});                }                fr(l - 1, 0)                {                    if (j / blockSize != lBlock)                        break;                    s[j / blockSize].erase(s[j / blockSize].find({a[j], j}));                    a[j] *= mul[j / blockSize], a[j] += add[j / blockSize];                    s[j / blockSize].insert({a[j], j});                }                add[lBlock] = 0, mul[lBlock] = 1;                fr(r, 0)                {                    if (j / blockSize != rBlock)                        break;                    s[j / blockSize].erase(s[j / blockSize].find({a[j], j}));                    a[j] *= mul[j / blockSize], a[j] += add[j / blockSize];                    if (c == 1)                        a[j] += x;                    else                        a[j] *= x;                    s[j / blockSize].insert({a[j], j});                }                f(r + 1, n)                {                    if (i / blockSize != rBlock)                        break;                    s[i / blockSize].erase(s[i / blockSize].find({a[i], i}));                    a[i] *= mul[i / blockSize], a[i] += add[i / blockSize];                    s[i / blockSize].insert({a[i], i});                }                add[rBlock] = 0, mul[rBlock] = 1;                lBlock++;                while (lBlock != rBlock)                {                    if (c == 1)                        add[lBlock] += x;                    else                        mul[lBlock] *= x, add[lBlock] *= x;                    lBlock++;                }            }        }        else        {            ll x;            cin >> x;            ll l = -1, r = -1;            ll mx = (n - 1) / blockSize, cur = 0;            while (cur <= mx)            {                ll y = x;                if (add[cur])                    y -= add[cur];                if (y < 0)                {                    cur++;                    continue;                }                if (mul[cur])                {                    if (y % mul[cur] == 0)                        y /= mul[cur];                    else                    {                        cur++;                        continue;                    }                }                auto it = s[cur].lower_bound({y, -1e18});                if (it != s[cur].end() && it->first == y)                {                    l = it->second;                    break;                }                cur++;            }            if (l == -1)            {                cout << "-1\n";                continue;            }            cur = mx;            while (cur >= 0)            {                ll y = x;                if (add[cur])                    y -= add[cur];                if (y < 0)                {                    cur--;                    continue;                }                if (mul[cur])                {                    if (y % mul[cur] == 0)                        y /= mul[cur];                    else                    {                        cur--;                        continue;                    }                }                auto it = s[cur].lower_bound({y + 1, -1e18});                if (it != s[cur].begin())                {                    it--;                    if (it->first == y)                    {                        r = it->second;                        break;                    }                }                cur--;            }            cout << r - l + 1 << "\n";        }    }#ifndef ONLINE_JUDGE    cout            << "\nTime Elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";#endif    return 0;}`

### Second solution

`INF = 1e9n = int(input())a = list(map(int, input().split(' ')))q = int(input())while q > 0:    query = list(map(int, input().split(' ')))    t = query[0]    if t == 1:        [l, r, x] = query[1:]        for i in range(l - 1, r):            if(a[i] <= INF):                a[i] += x    elif t == 2:        [l, r, x] = query[1:]        for i in range(l - 1, r):            if(a[i] <= INF):                a[i] *= x    else:        [z] = query[1:]        if not (z in a):            print(-1)        else:            print(len(a) - a[::-1].index(z) - a.index(z))    q -= 1`