Make n00b_land Great Again!
Practice
4.3 (20 votes)
Binary search algorithm
Bit
Medium
Tree
Segment tree
Problem
61% Success 2008 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code

Animesh is the mayor of n00b_land - a city known for it's massive production of antidepressants.

The rise in demand for such medications have attracted M avaricious businessmen, conveniently numbered from 1 to M, from all around the world. There are N factories in n00b_land - and each factory is owned by one of the M businessmen. Again, the factories are conveniently numbered from 1 to N. Moreover, some factories are dependent on other smaller factories to obtain their raw material. There are N - 1 dependencies in total. Factory numbered 1 is main factory and is not dependent on any other factory. For each factory numbered from 2 to N, it depends on exactly one other factory which has strictly lower index than it.
In other words, the network of dependencies between factories form a tree rooted at 1.

Every year, some factory F earns an amount X as donation from the generous people of pr0_land. The pr0 people of pr0_land ask the factory to distribute wealth in the following manner :

1) Add X to F.
2) Add X + D to all factories which are dependent on F.
3) Add X + 2*D to all factories which are dependent on any factory from step (2).
In general, add X + (K) * D to a factory G if there are K dependencies en-route from F to G.

The businessmen in n00b_land do not care about the welfare of the workers in the factories. As a result, they take all the money that a factory receives by donation from the pr0 people of pr0land.
Further, each businessman has a value Threshold(i), denoting the amount the ith businessman wants to earn.

Given the reports for Q consecutive years (Years are numbered 1..Q), your task is to find the year after which the ith businessman would have earned atleast Threshold(i).

Input Format :

The first line of input comprises space separated integers N and M.

The second line consists of N - 1 space separated integers . Here, ith integer parent[i] denotes parent of (i + 1)th numbered node.

The next line comprises N space separated integers :
The ith integer B[i] denotes the index of the businessman who owns the factory numbered i.

The next line comprises M space separated integers:
The ith integer threshold[i] denotes threshold money for ith businessman

The next line of input comprises one integer Q.
The next Q lines comprises three integers (F, X, D) each.

Constraints :

1 <= N <= 5 * 105
1 <= M <= 5 * 105
1 <= Q <= 5 * 105
1 <= parent[i] <= i
1 <= B[i] <= M
1 <= threshold[i] <= 1018
1 <= F <= N
1 <= X <= 106
0 <= D <= 106

For 15% tests, N,M,Q <= 2000
For 25% tests, D = 0
For rest, orignal constraints

Output Format :

Print M lines, where the ith line denotes the year after which the ith businessman earns his desired amount. If he doesn't earn it throughout the course of the Q years, print "rekt". (without quotes)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:10
10 votes
Tags:
Integer FactorizationAlgorithmsMathMathamaticsFactorizationNumber Theory
Points:50
6 votes
Tags:
LoopsHardTree
Points:30
39 votes
Tags:
Linear AlgebraApprovedEasy-MediumReadyMathematicsMatrix Exponentiation