COCI-11 (2011) - Γύρος #2 - 6 (Raspored)

View as PDF

Submit solution

Points: 45 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python
Raspored

Η πίτσα του Mirko είναι η καλύτερη στην πόλη. Είναι τόσο καλό που όλοι οι κάτοικοι της πόλης τρώνε πίτσα για μεσημεριανό κάθε μέρα. Η υπηρεσία παράδοσης της Mirko είναι τόσο γρήγορη που ο χρόνος παράδοσης είναι αμελητέος. Το πρόβλημα είναι να ψήνουν τις πίτσες, αφού όλοι οι κάτοικοι έχουν τον δικό τους αγαπημένο συνδυασμό επικάλυψης, οπότε το ψήσιμο πίτσας για δύο διαφορετικούς κατοίκους δεν απαιτεί πάντα τον ίδιο χρόνο. Το Mirko έχει μόνο έναν μικρό φούρνο ψησίματος με χωρητικότητα μίας πίτσας κάθε φορά, επομένως ο καλός προγραμματισμός είναι εξαιρετικά σημαντικός και πρέπει να καθοριστεί πριν ξεκινήσει η ημέρα.
Για καθέναν από τους N κατοίκους της πόλης (σημειωμένους με αριθμούς από το 1 έως το N) γνωρίζουμε τη διάρκεια ψησίματος για την αγαπημένη τους πίτσα (T_i), καθώς και τη στιγμή της ημέρας που σχεδιάζουν να γευματίσουν (L_i). Εάν ένας κάτοικος λάβει την πίτσα του K στιγμές πριν από την προγραμματισμένη ώρα του μεσημεριανού γεύματος, ο Mirko ανταμείβεται με ένα φιλοδώρημα K kunas1. Από την άλλη πλευρά, εάν η πίτσα παραδοθεί K στιγμές καθυστερημένη (μετά την προγραμματισμένη ώρα του γεύματος), ο Mirko πρέπει να πληρώσει τον κάτοικο K kunas (λόγω του ασφαλιστηρίου συμβολαίου έγκαιρης παράδοσης). Εάν η πίτσα παραδοθεί ακριβώς στην ώρα της, ο Mirko δεν θα λάβει φιλοδώρημα, αλλά δεν χρειάζεται να πληρώσει και τίποτα.
Ο Mirko θα ήθελε να μάθει το μέγιστο συνολικό φιλοδώρημα (συμπεριλαμβανομένων όλων των ασφαλιστικών πληρωμών ως αρνητικών φιλοδωρημάτων) που μπορεί να κερδίσει σε μια μέρα, εάν οι πίτσες ψηθούν με τη βέλτιστη σειρά. Παρατηρήστε ότι ο Mirko μπορεί να κερδίσει ένα αρνητικό συνολικό φιλοδώρημα (αν πρέπει να πληρώσει περισσότερη ασφάλιση από το ποσό των φιλοδωρημάτων που λαμβάνει).

Δεδομένου ότι οι κάτοικοι μερικές φορές αλλάζουν τις αγαπημένες τους γαρνιτούρες πίτσας, καθώς και την προτιμώμενη ώρα για μεσημεριανό γεύμα, το πρόγραμμα του Mirko πρέπει να προσαρμοστεί ώστε να συνεχίσει να κερδίζει τα βέλτιστα ποσά φιλοδωρήματος. Γράψτε ένα πρόγραμμα για τον υπολογισμό της μέγιστης συνολικής συμβουλής για τις απαιτήσεις έναρξης, καθώς και μετά από κάθε αλλαγή.
Σημείωση: Σε αυτήν την πόλη, η μέρα ξεκινά τη στιγμή t = 0 και διαρκεί πολύ περισσότερο από τον χρόνο που απαιτείται για το ψήσιμο της πίτσας για όλους τους κατοίκους. Το πρόγραμμα, συμπεριλαμβανομένων των προσαρμογών, πρέπει να καθοριστεί πριν από την έναρξη της ημέρας.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο θετικούς ακέραιους N και C, τον αριθμό των κατοίκων και τον αριθμό των αλλαγών που απαιτούνται για την πίτσα, αντίστοιχα.
Κάθε μία από τις επόμενες N γραμμές περιέχει δύο θετικούς ακέραιους αριθμούς: L_i, τη στιγμή που ο κάτοικος i σχεδιάζει να γευματίσει, και T_i, ο χρόνος που χρειάζεται για να ψήσει η πίτσα για τον κάτοικο i.
Κάθε μία από τις επόμενες C γραμμές περιέχει τρεις θετικούς ακέραιους αριθμούς: R (ο δείκτης ενός κατοίκου), L (η νέα στιγμή που ο κάτοικος R σχεδιάζει να γευματίσει) και T (ο χρόνος που χρειάζεται για να ψήσει τη νέα αγαπημένη πίτσα του κατοίκου R).
Περιορισμοί:
1 \leq N,\;C \leq 200\,000,
0 \leq L_i,\;L \leq 100\,000,
1 \leq T_i,\;T \leq 100\,000,
1 \leq R \leq N.

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει το μέγιστο συνολικό άκρο για τις αρχικές απαιτήσεις των κατοίκων.
Για κάθε μία από τις C αλλαγές, η έξοδος πρέπει να περιέχει μια πρόσθετη γραμμή εξόδου που περιέχει τη νέα μέγιστη συνολική τιμή κορυφής μετά την αλλαγή.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 50% των πόντων, ισχύει ο ακόλουθος περιορισμός: 1 \leq T_i,\;T \leq 1000.

Παραδείγματα

input

3 2
10 2
6 5
4 3
1 6 1
3 0 10

output

3
2
-11
Επεξήγηση του 1ου παραδείγματος:

Το βέλτιστο πρόγραμμα ψησίματος πίτσας είναι (1, 3, 2). Με αυτόν τον τρόπο, η πρώτη πίτσα θα τελειώσει τη στιγμή t = 2, η τρίτη στο t = 5 και η δεύτερη στο t = 10. Η πρώτη πίτσα θα παραδοθεί 8 λεπτά νωρίτερα (8 kuna φιλοδώρημα), η δεύτερη θα αργήσει 1 στιγμή (-1 kuna) και η τρίτη θα αργήσει 4 λεπτά (-4 kunas), οπότε το συνολικό φιλοδώρημα είναι 3 kuna. Όταν ο πρώτος κάτοικος αλλάζει απαιτήσεις, το βέλτιστο πρόγραμμα παραμένει αμετάβλητο, ενώ οι συμβουλές αλλάζουν σε 5, 0 και -3, αντίστοιχα. Μετά τη δεύτερη αλλαγή απαίτησης, το βέλτιστο πρόγραμμα είναι (1, 2, 3), ενώ οι συμβουλές είναι 5, 0 και -16, αντίστοιχα.


input

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

output

-8
-13
-18

input

6 7
17 5
26 4
5 5
12 4
8 1
18 2
3 31 3
4 11 5
4 19 3
5 23 2
6 15 1
5 19 1
3 10 4

output

27
59
56
69
78
81
82
58

Kuna - Κροατικό νόμισμα. 1 kuna = 100 lipa(s); 1 € = περίπου 7,5 kuna(s).


Comments

There are no comments at the moment.