Member 14812390 Ответов: 0

Примените алгоритм МО к диапазону запросов


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.


Что я уже пробовал:

#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];
    }

    }

    }

Patrice T

Дайте ссылку на проблему на сайте challenge.
В этих проблемах каждое слово имеет значение.

Member 14812390

Ссылка на вопрос: https://www.hackerearth.com/challenges/competitive/april-circuits-20/algorithm/happy-segments-e290faa6/

0 Ответов