---{"category_name":"easy","problem_code":"CHARGE","problem_name":"Charge Scheduling","problemComponents":{"constraints":"- $1 \\leq Q \\leq 3 \\cdot 10^5$\n- $1 \\leq N \\leq 3 \\cdot 10^5$\n- $0 \\leq A_i \\leq 3 \\cdot 10^5$ for each valid $i$\n- $0 \\leq T_i \\leq 3 \\cdot 10^5$ for each valid $i$\n- The sum of $N$ over all testcases does not exceed $ 3 \\cdot 10^5$","constraintsState":true,"subtasks":"- **Subtask #1 (10 points)** : $T_i$-s are equal for all $N$ people\n- **Subtask #2 (90 points)** : Original constraints\n","subtasksState":true,"inputFormat":"- The first line contains a single integer $Q$ denoting the number of test cases. The description of $Q$ test cases follows.\n- Each test case contains $3$ lines of input.\n- The first line of each test case contains a single integer $N$, the number of people on the train.\n- The second line of each test case contains $N$ space-separated integers, $A_1, A_2, \\dots A_N$, where $A_i$ is the amount of time that the $i^{th}$ person needs to use the charger.\n- The third line of each test case contains $N$ space separated integers, $T_1, T_2, \\dots T_n$, where $T_i$ is the time at which the $i^{th}$ person leaves the train.","inputFormatState":true,"outputFormat":"- For each test case, in the first line, print a single integer $M (\\leq 2N)$, the number of different intervals that you want to schedule.\n- $M$ lines follow. For each valid $i$, the $i^{th}$ of these lines should contain three space-separated integers, $i, L, R$ denoting that the person $i$ should use the charging station from $[L, R)$.\n- The number of satisfied people should be maximum.\n- The scheduling should be valid.\n- It is possible to schedule the same person multiple times.\n- The order in which the intervals are displayed does not matter.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"4\n5\n31 32 6 13 7\n14 50 34 4 31\n5\n43 26 22 11 30\n26 4 41 46 49\n5\n36 40 49 19 37\n18 11 48 15 33\n5\n16 3 24 21 21\n24 31 36 49 50","output":"3\n3 0 6\n5 6 13\n2 13 45\n2\n4 0 11\n3 11 33\n0\n3\n2 0 3\n1 3 19\n4 19 40","explanation":"**Test case 1**: Person $1$ and Person $4$ can never be satisfied because the time they spend on the train ($14$ and $4$ respectively) is less than the amount of time they want to spend for charging. The other three people can be assigned as shown (Person $3$ in the interval $[0, 6)$, Person $5$ in the interval $[6, 13)$ and finally Person $2$ in the interval $[13, 45)$. Note that there are multiple solutions, for example, we could have also assigned Person $5$ to $[0, 7)$ and Person $3$ to $[7, 13)$ instead. Both are considered correct.\n\n**Test case 2**: Person $1$ and Person $2$ can never be satisfied (they spend less time on the train than the amount of time they need to use the charging station). Among the remaining three, we cannot satisfy all of them, since the total time required would be $30 + 11 + 22 = 63$, but $t = 49$, all of them would have left the train. However we can select either Persons $3$ and Person $4$ or Person $4$ and Person $5$ and schedule them in any order, and in both cases, both of the persons would be satisfied.\n\n**Test case 3**: No one can be satisfied and hence the answer is $0$.\n\n**Test case 4**: Apart from Person $2$ (who has a very low charging time), we cannot hope to satisfy more than $2$ of the others. This is because the sum of the $3$ least times is already $58$ and everyone would have left the train by $t = 50$. Therefore the maximum number of people we can hope to satisfy is $3$, and the given solution constructs it.","isDeleted":false}}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"srikkanth_adm","problem_tester":"","date_added":"31-07-2021","tags":{"0":"aug21","1":"aug21","2":"constructive","3":"constructive","4":"easy","5":"easy","6":"greedy","7":"greedy","8":"srikkanth_adm"},"problem_difficulty_level":"Unavailable","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/CHARGE","time":{"view_start_date":1629117000,"submit_start_date":1629117000,"visible_start_date":1629117000,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=CHARGE","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Bengali](https://www.codechef.com/download/translated/AUG21/bengali/CHARGE.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/AUG21/mandarin/CHARGE.pdf), [Russian](https://www.codechef.com/download/translated/AUG21/russian/CHARGE.pdf), and [Vietnamese](https://www.codechef.com/download/translated/AUG21/vietnamese/CHARGE.pdf) as well.There are $N$ people in a train and each of them gets on the train at time $t = 0$.Each person on the train wants to use the charging station on the train for some amount of time, but unfortunately, the train has only one charging station and can only be used by $1$ person at any point in time.The $i^{th}$ person wants to use the charging station for $A_i$ minutes in total and will leave the train at time $T_i$.A person will be satisfied after the journey, only if that person gets to use the charging station for the desired amount of time.Find a way to schedule the charging such that a maximum number of people is satisfied.In order to schedule, you can pick any interval of time, say $[L, R)$, and ask the person $i$ to use the charging station from $t = L$ and leave just before $t = R$.After this the person $i$ would have spent $R - L$ minutes on the charging station and any person who is still on the train can begin using the charging station starting from $t = R$.An interval scheduling will be a set of time intervals and people assigned to those intervals.A schedule is **valid** if:- No two intervals in the schedule intersect each other. Note that all $[L, R)$ and $[R, S)$ do not intersect each other.- For all people $i$ and all intervals $[L, R)$ assigned to $i$, $0 \leq L \leq R \leq T_i$, i.e. each person is not assigned to an interval of time when they are not on the train.You have to find optimal scheduling that does not contain more than $2N$ intervals.It is guaranteed that there always exists optimal scheduling with the given constraints.If there are many such schedules, you can output any of them.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>