K3CHKEQ - Editorial

PROBLEM LINK: Check Equal!

Author: Soumy Jain
Tester: Divyank Goyal
Editorialist: Soumy Jain




Array and Precomputations


Let’s define ans_{i} to have the index of an element on left of i which is not equal to v_{i}. Obviously, ans_{1} = -1 because no element occur before first index. Now if, v_{i} != v_{i-1} we can directly mark ans_{i} to be i-1.

Now what if v_{i} == v_{i-1}? In this case we can mark ans_{i} = ans_{i-1}.

Now to answer the query, we can first check if v_{r} != k,
if it is true we can directly print “NO”,
else we will find the index of the element on the left which is not equal to k using ans_{r} and check if it lies in range or not.


Setter's Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
    ll n;
    cin >> n;
    vector<ll> v(n);
    for (auto &i : v)
        cin >> i;
    vector<ll> ans(n);
    ans[0] = -1;
    for (ll i = 1; i < n; i++)
        if (v[i] != v[i - 1])
            ans[i] = i - 1;
            ans[i] = ans[i - 1];
    ll q;
    cin >> q;
    while (q--)
        ll l, r, k;
        cin >> l >> r >> k;
        l--, r--;
        if (v[r] == k && ans[r] < l)
            cout << "YES\n";
            cout << "NO\n";
    return 0;