HackerEarth The maximum distance problem solution YASH PAL, 31 July 2024 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: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.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.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 << "-1n"; 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 << " sn";#endif return 0;}Second solutionINF = 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 coding problems solutions