K3CHKEQ - Editorial

editorial
, ,
1

PROBLEM LINK: Check Equal!

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

DIFFICULTY:

MEDIUM

PREREQUISITES:

Array and Precomputations

EXPLANATION:

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.

SOLUTIONS:

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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;
        else
            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";
        else
            cout << "NO\n";
    }
    return 0;
}