### broly_1033's blog

By broly_1033, history, 6 months ago,

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

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


• +1

 » 6 months ago, # |   0 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>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.
•  » » 6 months ago, # ^ |   0 Oh my bad! Carelessness on my part, I have corrected the code. But now it's giving wrong answer on Test case 5.