DMOPC '19 Contest 6 P6 - Math is Difficult

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 3.0s
Memory limit: 256M

Problem type

Tzovex is currently taking a course in real analysis. Unfortunately for him and his class, they are having trouble following the lectures and are now struggling with a particular homework assignment that is due in D+1 days. The homework assignment consists of M questions, the ith of which has a value of v_i. Including himself, Tzovex's class consists of N students, the jth of which having solved the first a_j problems while being unable to solve the rest. However, the professor is willing to help out students in extra classes, each of which is dedicated to a single problem. In particular, help will be available for the ith problem between l_i and r_i (inclusive) days from today. The jth student only has time for one extra class, and he can only attend it if it happens in exactly d_j days. The professor also has a unique way of grading assignments. Rather than giving the students marks, he instead gives them penalties. Going from the first to the last problem, the kth problem that a student did not solve will earn them k times the value of the problem in penalties. Assuming that no student will solve any extra problems on their own, determine the minimum possible penalty that each of the N students can achieve.

Input Specification

The first line contains three space-separated integers, N, M, and D.
M lines follow, the ith of which contains three space separated integers, v_i, l_i, and r_i.
N more lines follow, the jth of which contains two space separated integers, a_j and d_j.

Output Specification

Output N lines, the jth of which containing a single integer, the minimum possible penalty that the jth student can achieve.


In all subtasks,
1 \le N,M,D \le 200\,000
1 \le v_i \le 10^6
0 \le a_j \le M
1 \le d_j,l_i,r_i \le D
l_i \le r_i

Subtask 1 [5%]

1 \le N,M,D \le 300

Subtask 2 [10%]

1 \le N,M,D \le 5\,000

Subtask 3 [35%]

l_i=1 and r_i=D

Subtask 4 [50%]

No additional constraints.

Sample Input

5 4 5
5 3 5
2 1 3
3 2 4
7 4 5
0 4
1 3
2 5
3 2
4 1

Sample Output


Explanation for Sample Output

The optimal move for student 1 is to attend the lecture for problem 4 resulting in a penalty of 1(5)+2(2)+3(3)=18.
The optimal move for student 2 is to attend the lecture for problem 3 resulting in a penalty of 1(2)+2(7)=16.
The optimal move for student 3 is to attend the lecture for problem 4 resulting in a penalty of 1(3)=3.
Student 4 can't attend any useful lectures and so has a penalty of 1(7)=7.
Student 5 doesn't need any lectures and has a penalty of 0.


There are no comments at the moment.