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 << "-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 = 1e9
n = 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
0 Comments