36ος ΠΔΠ B' Φάση Γυμνασίου
All that jazz (allthatjazz)

Στη Σταυρούλα αρέσει πολύ η μουσική τζαζ. Όταν της πέφτει το λαχείο, αποφασίζει να κάνει ένα ταξίδι στη Νέα Ορλεάνη και να παρακολουθήσει όσο περισσότερες συναυλίες τζαζ μπορεί. Βοηθήστε την να προγραμματίσει το ταξίδι της!

Στο προσεχές μέλλον πρόκειται να γίνουν \(N\) συναυλίες τζαζ στη Νέα Ορλεάνη και, για κάθε συναυλία \(i\), είναι γνωστή η ημερομηνία \(D_i\) που θα γίνει. Χάριν ευκολίας, σε αυτό το πρόβλημα έχουμε αντικαταστήσει τις ημερομηνίες με θετικούς ακέραιους αριθμούς: η μέρα \(1\), η μέρα \(2\), κ.ο.κ.

Η Σταυρούλα δεν έχει αποφασίσει ακόμα πότε θα πάει ούτε πόσες μέρες θα μείνει στη Νέα Ορλεάνη. Θέλει να τη βοηθήσετε να αποφασίσει, απαντώντας συνολικά \(Q\) ερωτήματα που το καθένα είναι της μορφής: “αν πάω για \(K_i\) μέρες στη Νέα Ορλεάνη και προγραμματίσω την αναχώρησή μου όσο καλύτερα γίνεται, πόσες είναι οι περισσότερες συναυλίες που μπορώ να παρακολουθήσω;”

Θεωρήστε δεδομένο ότι η Σταυρούλα θα μπορεί να παρακολουθήσει όλες τις συναυλίες που γίνονται σε όλο το διάστημα της παραμονής της στη Νέα Ορλεάνη, συμπεριλαμβανομένης της πρώτης και της τελευταίας μέρας, και επίσης ότι θα μπορεί να παρακολουθήσει ακόμα και περισσότερες από μία συναυλίες που γίνονται την ίδια μέρα.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει τις πληροφορίες των συναυλιών και τα ερωτήματα της Σταυρούλας και θα τα απαντά.

Αρχεία Εισόδου:

Τα αρχεία εισόδου με όνομα allthatjazz.in είναι αρχεία κειμένου με την εξής δομή:

Στην πρώτη γραμμή υπάρχει ένας θετικός ακέραιος αριθμός: το πλήθος των συναυλιών \(N\).
Η δεύτερη γραμμή περιέχει ακριβώς \(N\) ακέραιους αριθμούς \(D_i\) (όπου \(1 \le i \le N\)), χωρισμένους ανά δύο με ένα κενό διάστημα: την ημέρα που γίνεται κάθε μία από τις \(N\) συναυλίες.
Στην τρίτη γραμμή υπάρχει ένας θετικός ακέραιος αριθμός: το πλήθος των ερωτήσεων \(Q\).
Η τέταρτη γραμμή περιέχει ακριβώς \(Q\) ακέραιους αριθμούς \(K_i\) (όπου \(1 \le i \le Q\)), χωρισμένους ανά δύο με ένα κενό διάστημα: τη διάρκεια σε ημέρες του ταξιδιού της Σταυρούλας για το \(i\)-οστό ερώτημα.

Αρχεία εξόδου:

Τα αρχεία εξόδου με όνομα allthatjazz.out είναι αρχεία κειμένου με την εξής δομή. Πρέπει να περιέχουν ακριβώς \(Q\) γραμμές που κάθε μία να περιέχει ακριβώς έναν ακέραιο αριθμό: την απάντηση στο \(i\)-οστό ερώτημα, κατά σειρά.

Περιορισμοί:

\(1 \le N \le 1.000.000, 1 \le Q \le 1.000.000\) και \(N\times Q \le 2.000.000\).
\(1 \le D_i \le 1.000.000.000\) για κάθε \(i\), όπου \(1 \le i \le N\).
\(1 \le K_i \le 1.000.000.000\) για κάθε \(i\), όπου \(1 \le i \le Q\).

Παράδειγμα αρχείων εισόδου-εξόδου:

allthatjazz.in	allthatjazz.out
6 7 4 2 5 4 3 7 3 4 2 1 6 2 5	4 5 3 2 6 3 5

Εξήγηση παραδείγματος:

Πρόκειται να γίνουν συνολικά \(N=6\) συναυλίες. Η πρώτη είναι τη μέρα \(7\), η δεύτερη τη μέρα \(4\), η τρίτη τη μέρα \(2\), κ.ο.κ. Προσέξτε ότι τη μέρα \(4\) θα γίνουν δύο συναυλίες. Προσέξτε επίσης ότι κάποιες μέρες, π.χ. τη μέρα \(1\) και τη μέρα \(6\), δε θα γίνει καμία συναυλία.

Πρέπει να απαντήσουμε σε \(Q=7\) ερωτήματα:

\(K=3\), δηλαδή αν η Σταυρούλα μείνει \(3\) μέρες στη Νέα Ορλεάνη, πόσες είναι οι περισσότερες συναυλίες που μπορεί να παρακολουθήσει; Αν φτάσει τη μέρα \(2\) και μείνει μέχρι και τη μέρα \(4\) (συνολικά \(3\) μέρες) θα παρακολουθήσει συνολικά \(4\) συναυλίες: μία τη μέρα \(2\), μία τη μέρα \(3\) και δύο τη μέρα \(4\). Αυτό είναι το μέγιστο που μπορεί να πετύχει για \(3\) μέρες παραμονής.
\(K=4\). Από τη μέρα \(2\) μέχρι και τη μέρα \(5\), συνολικά \(5\) συναυλίες.
\(K=2\). Από τη μέρα \(3\) μέχρι και τη μέρα \(4\), συνολικά \(3\) συναυλίες.
\(K=1\). Μόνο τη μέρα \(4\), συνολικά \(2\) συναυλίες.
\(K=6\). Από τη μέρα \(2\) μέχρι και τη μέρα \(7\), και τις \(6\) συναυλίες.
\(K=2\). Το ίδιο ερώτημα έχει ήδη απαντηθεί.
\(K=5\). Από τη μέρα \(1\) μέχρι και τη μέρα \(5\), συνολικά \(5\) συναυλίες.

Παρατηρήσεις:

Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.