### AshrafSustS19's blog

By AshrafSustS19, history, 10 months ago,

For offline queries, we can sort them using sqrt decomposition to minimize query traversal costs. This is very useful especially in situations where query answers can be generated using two pointers method. For this, we first divide the total query range in sqn = sqrt(n) sections. We first sort the queries in order of which section the starting point fell in, than in each section we sort the queries based on the order ending point from large to small or (small to large). I used a slightly altered implementation for this problem. Instead of using large to small or small to large endpoint at section. I sorted them in an altering structure. Therefore, if in section 1, we sort them from large to small, in section 2 we sort them from small to large, then in section 3 we again sort them from large to small. I think this implementation is quite faster on average, and in the problem I tested both the default and customized implementation. The latter proved to be almost twice as fast as the former. The implementation is as follows

struct Qry{
lli l, r, ind;
Qry(lli _l, lli _r, lli _ind){
l = _l, r = _r, ind = _ind;
}
};

bool cmp(Qry &a, Qry &b){
if (a.l / sqn < b.l / sqn) return true;
else if ((a.l / sqn == b.l / sqn)){
if ((a.l / sqn) % 2 == 0){
return a.r < b.r;
}
else {
return a.r > b.r;
}
}
return false;
}

• -11

 » 10 months ago, # |   0 go learn binary search
•  » » 10 months ago, # ^ |   0 Solve 86D - Powerful array with binary search only, I will consider "go learn binary search" then
•  » » » 10 months ago, # ^ | ← Rev. 2 →   -10 at your level, you will never need to solve a problem that requires that much DS knowledge in contest.
•  » » » » 10 months ago, # ^ |   0 I practice 1900-2000 rating problems, and I don't see how learning "binary search" deals with 1900-2000 problems. Please kindly explain.
•  » » » » » 10 months ago, # ^ |   0 It's a joke. In short, I mean at your current level you don't need to learn any heavy data structures/algorithms. Just solving/practicing adhoc, constructive, and practicing problem solving in general should be enough.
•  » » » » » » 10 months ago, # ^ |   0 Very lame and derogatory way of making a joke, you talk like a child
•  » » » » » » » 10 months ago, # ^ |   0 ok adult sir
•  » » » » 10 months ago, # ^ |   +1 If his wish is not improving rating then you can't talk like that. Many of us just love solving problems,rather than ranting about rating. But if he ever posts "why my rating is still stuck at 1400 despite solving > 2200" then your comment will be a sledgehammer to that post.