harsh-apcr's blog

By harsh-apcr, history, 3 months ago,

I just learned about Mo's algorithm and went to solve some problems.

here is the problem link where I'm stuck : https://www.spoj.com/problems/DQUERY/

I used the standard implementation of Mo's algorithm from cp-algorithms here : https://cp-algorithms.com/data_structures/sqrt_decomposition.html

My solution is giving TLE (I'm pasting my code here)

map<int, int> mp;
vector<int> a;
int sz;
class Query {
public:
int l, r, idx;

bool operator<(const Query &other) {
return make_pair(this->l/sz, this->r) < make_pair(other.l/sz, other.r);
}
};
inline void remove(int idx) {
int x=a[idx];
mp[x]-=1;
if (mp[x]==0) mp.erase(x);
}
mp[a[idx]]+=1;
}
return mp.size();
}

void solve() {
int n;cin>>n;
a.assign(n, 0);
for(int i=0;i<n;i++) cin>>a[i];
sz=(int)ceil(sqrt(n));
int q;cin>>q;
vector<Query> queries;
for(int j=0;j<q;j++) {
int l, r;cin>>l>>r;
--l, --r;
queries.push_back({l, r, j});
}
// Mo's algorithm
sort(queries.begin(), queries.end());
int curl=0, curr=-1;
for(Query query : queries) {
while (curl>query.l) {
curl--;
}
while (curr<query.r) {
curr++;
}
while (curl<query.l) {
remove(curl);
curl++;
}
while (curr>query.r) {
remove(curr);
curr--;
}

 » 3 months ago, # | ← Rev. 2 →   +5 Use the add and erase function like this and use an 1e6 size array to store the values instead of using map. Add and Erase Functioninline void add( int idx ){ freq[a[idx]]++; if ( freq[a[idx]] == 1 ) count++; } inline void erase( int idx ){ freq[a[idx]]--; if ( freq[a[idx]] == 0 ) count--; } inline int get_answer() { return count; } 
•  » » 3 months ago, # ^ |   +1 Thanks, never thought $\log n$ complexity factor can also get TLE
 » 3 months ago, # | ← Rev. 2 →   +1 $O(n\sqrt{n}\log n)$ is an altogether evil complexity and should be avoided at all costs.https://codeforces.com/blog/entry/100910