Click here to Skip to main content
15,888,527 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Can anyone tell me how to use MO's algorithm here in this code for a range of queries? I am getting TIME LIMIT EXCEEDED on running the below given code.

The problem statement is as follows: You are given two arrays, array A of size n and array B of size m. Array A will have integers from 1 to m and array B has expected occurrence of each number present in array A. Now you have queries in the form of range and if for given range, occurrence of each number in that range of array A is equal to its expected occurrence present in array B, then you have to print 1,otherwise 0.


What I have tried:

#include<bits/stdc++.h>
      using namespace std;
      #define ll long long int
      int main() 
     {
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
 
      ll n, m, i;
     cin >> n >> m;
    ll arr[n], arr1[m],freq[m];

     for (i = 0; i < n; i++)
    {
    cin >> arr[i];
     }
    for (i = 0; i < m; i++)
    {
    cin >> arr1[i];
    freq[i]=arr1[i];
    }

    ll q;
    cin >> q;

    while (q--) 
    {
    ll low, high;
    cin >> low >> high;

    ll good = 1;

    for (i = low - 1; i < high; i++) {
        freq[arr[i] - 1]--;
    }

    for (i = low - 1; i < high; i++)
    {
        if (freq[arr[i] - 1] != 0) 
        {
            good = 0;
            break;
        }
    }
    cout << good << '\n';

     for(i=0;i<m;i++)
     {
        freq[i]=arr1[i];
    }

    }

    }
Posted
Comments
Patrice T 24-Apr-20 15:12pm    
Give link to the problem on the challenge site.
In those problems, every word count.
Member 14812390 25-Apr-20 2:13am    
Link to the question: https://www.hackerearth.com/challenges/competitive/april-circuits-20/algorithm/happy-segments-e290faa6/

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900