DCP-315: Sanvi and chocolates-2 Back to All Problems

Hard Data Structures > Segment Tree/Interval Tree

**Sanvi** is a very cute girl. She likes chocolates so much. There are **N** chocolate boxes numbered from **1** to **N**, arranged linearly from left to right. Sanvi has a list of favorite chocolate boxes. She always takes chocolate only from these boxes. Sanvi has **M** friends numbered from **2** to **M+1**. Her id number is **1**. Like Sanvi, her friends also has list of favorite chocolate boxes. All the chocolate boxes are initially empty. Sanvi recently builds a robot which can add chocolate to these boxes. The robot operates total **D** days. Every day, the robot starts from some box numbered **L** and goes upto box **R** and add **C** chocolates to every boxes from left (L) to right(R) inclusive. Your task is to process **Q** wishes of Sanvi and her friends. Every wish start with id of friend -**X** and total number of chocolates he/she wants to collect-**Y**. You have to find the total number of days required to fulfill his/her wish. He/She always collects chocolates from his/her favorite chocolate boxes. **Note:** total ***distinct*** Yi for each Xi will be at most **15** ![enter image description here][1] ![enter image description here][2] Input: ------ Input starts with four integers **N,M,D,Q** denoting respectively total boxes, number of Sanvi's friends, total operation days of robot and total wishlist. For each person with id from **1** to **M+1**, there will be one line of input that starts with ***Ti*** denoting total number of favorite boxes of ith person. Then space separated ***Ti*** integers denoting favorite box id of ith person. Then there will be **D** more lines with space separated three integers ***Li, Ri , Ci*** as explained above. Then there will be **Q** more lines with space separated two integers ***Xi, Yi*** as explained above. ---------- Constraints: --------------- **1<=N,M,D<=50000** **1<=Q<=100000** **1<=X<=M+1, 1<=L<=R<=N** **1<=C,Y<=1000000000** - total summation of favorite chocolate count will be at most **200000**. - In **Q** wishlists, **total distinct Yi** for each **Xi** will be at most **15**. ---------- Output: ------- For every **Q** wishes output a line of output denoting total number of days required to fulfill that wish.if it is not possible to fulfill wish, output **-1** instead. Sample Input ------------ 3 3 3 4 2 2 3 2 1 3 1 2 1 1 1 1 3 3 3 6 1 2 2 4 1 4 4 1 2 3 4 Sample Output ------------- 1 3 2 -1 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/99a3e085-c018-ce96-6c49-08d488b654f1_580097342030471b884ace3e66f6d3e0_W280xH200.png [2]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/3fd51c42-2f92-c863-0dec-08d488b698dd_399edca124db4d71b79dfe6ca0cd2f49_W262xH204.png

Problem Setter:

Bishal Gautam

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 4.00
C++ 4.00
C++14 4.00
C# 5.00
Go 5.00
Java 5.00
JavaScript 5.00
Objective-C 5.00
Perl 5.00
PHP 4.00
Python 5.00
Python3 5.00
Ruby 5.00
VB.Net 5.00

Problem Stats




# User Language Timing
01 curiousblue Cpp14 0.32s
02 sahedsohel Cpp14 0.34s
03 seyedssz Cpp14 0.44s
04 BishalG Cpp14 0.45s
05 Robbinb1993 Cpp14 0.61s
06 khatribiru Cpp14 0.96s
07 Morass Cpp14 1.04s

Your feedback is our precious!

Or call +88 02 9853138 for support