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