I want to find out time complexity and space complexity of this code.

https://cses.fi/paste/4c432ea7de710eac40593c/

I was trying to solve this task but I was getting TLE.

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

1 | jiangly | 3678 |

2 | Benq | 3602 |

3 | ecnerwala | 3542 |

4 | maroonrk | 3541 |

5 | cnnfls_csy | 3540 |

6 | orzdevinwang | 3493 |

7 | inaFSTream | 3478 |

8 | Um_nik | 3430 |

9 | Geothermal | 3409 |

9 | Rebelz | 3409 |

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

1 | maomao90 | 174 |

2 | adamant | 164 |

3 | TheScrasse | 161 |

3 | SecondThread | 161 |

3 | awoo | 161 |

6 | nor | 159 |

7 | maroonrk | 158 |

8 | Um_nik | 156 |

9 | BledDest | 145 |

9 | Geothermal | 145 |

I want to find out time complexity and space complexity of this code.

https://cses.fi/paste/4c432ea7de710eac40593c/

I was trying to solve this task but I was getting TLE.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2024 18:07:01 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by .dragonman164 (previous revision, new revision, compare).Wow, you really have no clue. I guess you just think that segment tree is magic.

Time complexity is $$$O(n \log^2 n + qn \log n)$$$, space complexity is $$$O(n \log n + qn)$$$ ($$$qn$$$ part might not be true, I'm not sure how is it measured).

Lol!!! I got it. Thanks!!!!