Can anyone please tell me the process how to solve this problem . Thanx in advance :)

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3772 |

3 | tourist | 3706 |

4 | maroonrk | 3609 |

5 | Um_nik | 3591 |

6 | fantasy | 3526 |

7 | ko_osaga | 3500 |

8 | inaFSTream | 3477 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 183 |

2 | awoo | 180 |

3 | nor | 172 |

4 | -is-this-fft- | 171 |

5 | adamant | 170 |

6 | maroonrk | 165 |

7 | antontrygubO_o | 161 |

8 | SecondThread | 159 |

9 | dario2994 | 152 |

9 | kostka | 152 |

Can anyone please tell me the process how to solve this problem . Thanx in advance :)

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/21/2023 16:30:53 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Fix two rows and consider all cells between them as an single array... From left to right count for each position the subarrays ending in it, that subarray sum is between A and B, this can be done in for fixed rows (with a binary indexed tree), and overall time ...

... which will probably not fit in the time limit. You should remember about two pointers method when you come up with a binary search solution — perhaps it would make the solution faster.

you are right, but my pass in time... but i have to recognize than two pointer method is even better...

can you explain how to use that BIT ? Thanks!

we are going to solve the problem with 1D array

L= {x_{1},x_{2}, ...,x_{n}}, let bes_{i}=x_{1}+x_{2}+ ... +x_{n}, ands_{0}= 0. processLfrom left to right, if we have an structure that allow us to know how many elements are in range [a,b] when we processx_{i}, if it is the last element in a subarray whose sum is in [a,b], then existss_{j}(j<i) such thata≤s_{i}-s_{j}≤b, or the sames_{i}-b≤s_{j}≤s_{i}-a, then we can add to our solution how manys_{j}are in this range, and adds_{i}to the structure for future queries. We can use a treap, but if we process and compress in advance alls_{i}, we can use a BIT and the implementation would be easier.Your text to link here...