broly_1033's blog

By broly_1033, history, 11 months ago, In English

Hello everyone, I was learning about square root decomposition and Mo's algorithm and was practicing a few questions. I believe I have understood the concept. So I was trying problem 221D, and I've written the code and it works too, but I am getting TLE on submitting it. I was using coordinate compression as range was 10^9, then realized that for numbers >10^5 the condition won't be met so they are of no use. I am sorting using custom comparators, also included fast input/output. Then I removed the use of sorting queries for final answer by directly using the query id and storing the answer in a new array 'ans', which I can directly print. Can anyone look at the code, and suggest why am I still getting TLE on test case 5(I am stuck for the past 1 day)? Thank you!

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5;
class query{
public:
    int l, r, id, block, res;
} q[2*N];

int freq[N+5];
int xx = 0;

void add(vector<int>& v, int i) {

    if(v[i]>N) return; // as 10^5 is the maximum size of array
    // x>10^5, can ever have freq[x] = x

    freq[v[i]]++;
    if(freq[v[i]]==v[i]) xx++;
}
void rem(vector<int>& v, int i) {

    if(v[i]>N) return;

    if(freq[v[i]]==v[i]) xx--;
    freq[v[i]]--;
}

// Code for coordinate compression

//vector<int> d;
//void add(vector<int>& v, int i) {
//
//    if(v[i]>=N) return;
//
//    freq[v[i]]++;
//    if(freq[v[i]]==d[v[i]]) xx++;
//}
//void rem(vector<int>& v, int i) {
//
//    if(v[i]>=N) return;
//
//    if(freq[v[i]]==d[v[i]]) xx--;
//    freq[v[i]]--;
//}
//
//void coordinateCompression(vector<int>& v) {
//    d = v;
//    sort(d.begin(), d.end());
//    d.resize(unique(d.begin(), d.end()) - d.begin());
//    for (int i = 0; i < v.size(); ++i) {
//        v[i] = lower_bound(d.begin(), d.end(), v[i]) - d.begin();
//    }
//}

int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, m; cin>>n>>m;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin>>v[i];

//    coordinateCompression(v);

    int sz = sqrt(n)+1;

    int l, r;
    for(int i=0; i<m; i++) {
        cin>>l>>r;
        q[i].l = l-1; q[i].r = r-1;
        q[i].id = i;
        q[i].block = i/sz;
    }

    // sorting using custom comparator
    sort(q, q+m, [&](query a, query b){
        if(a.block==b.block) return a.r<b.r;
        return a.block<b.block;
    });

    int x = 0, y = 0;
    memset(freq, 0, sizeof(int)*(N+5));

    int ans[m];
    memset(ans, 0, sizeof(int)*m);

    for(int i=0; i<m; i++) {

        while(y<=q[i].r) {
            add(v, y);
            y++;
        }
        while(y>q[i].r+1) {
            y--;
            rem(v, y);
        }
        while(x<q[i].l) {
            rem(v, x);
            x++;
        }
        while(x>q[i].l) {
            x--;
            add(v, x);
        }

        // instead of sorting q with id, use id to create new ans array
        // in sorted manner

//        q[i].res = xx;
        ans[q[i].id] = xx;

    }

//    sort(q, q+m, [&](query a, query b){
//        return a.id<b.id;
//    });

    for(int i=0; i<m; i++) {
//        cout<<q[i].res<<'\n';
        cout<<ans[i]<<'\n';
    }


return 0;
}
 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The code for Mo's algorithm should look like this:

bool isLess(Query a, Query b):
  if a.l / K != b.l / K:
    return a.l < b.l
  return a.r < b.r 

And your code looks like this:

for(int i=0; i<m; i++) {
    cin>>l>>r;
    q[i].l = l-1; q[i].r = r-1;
    q[i].id = i;
    q[i].block = i/sz;
}

See the difference? q[i].block must be q[i].l / sz, not i / sz.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh my bad! Carelessness on my part, I have corrected the code. But now it's giving wrong answer on Test case 5.