35ος ΠΔΠ Γ' Φάση
Νησιά (islands)

Για τις καλοκαιρινές σου διακοπές, αποφάσισες να επισκεφθείς \(N\) ελληνικά νησιά. Όλο τον χρόνο προγραμμάτιζες τις λεπτομέρειες του ταξιδιού: ποια νησιά θα επισκεφθείς, με ποια σειρά, τι αξιοθέατα πρέπει οπωσδήποτε να δεις…

Επειδή ακόμα δεν κατέληξες πόσο θέλεις να μείνεις σε κάθε νησί, αγοράζεις \(N-1\) ανοιχτά εισιτήρια της εταιρείας “Φθηνές αναξιόπιστες Lines”, ένα για κάθε ζεύγος συνεχόμενων νησιών που θέλεις να επισκεφθείς. Έτσι, για κάθε νησί \(i\), μπορείς να ταξιδέψεις στο νησί \(i+1\) όποτε θελήσεις. Θεωρούμε ότι τα νησιά είναι αριθμημένα από \(1\) μέχρι \(N\).

Ξέχασες όμως τι λέει ο θυμόσοφος λαός: “Όταν ο άνθρωπος κάνει σχέδια, ο Θεός γελάει”. Η “Φθηνές αναξιόπιστες Lines” ανακοινώνει απεργίες. Έτσι αναγκάζεσαι να κάνεις αλλαγές στο ταξίδι σου. Επιμένεις όμως στην σειρά με την οποία θες να επισκεφθείς τα νησιά.

Πιο συγκεκριμένα, η “Φθηνές αναξιόπιστες Lines” μπορεί ανά πάσα στιγμή να διακόψει τις διαδρομές μεταξύ κάποιων νησιών. Αντίστοιχα, αν ικανοποιηθούν τα αιτήματα των εργαζομένων της, μπορεί ανά πάσα στιγμή να ανακοινώσει επανέναρξη κάποιων διαδρομών.

Εάν βρίσκεσαι σε κάποιο νησί \(i\) και θες να μετακινηθείς στο επόμενη νησί \(i+1\), αλλά αυτή η διαδρομή έχει διακοπεί λόγω των απεργιών, τότε μπορείς να πληρώσεις για ένα νέο εισιτήριο από μία άλλη εταιρεία, την “Ακριβές αξιόπιστες Lines”. Αντίθετα, αν η διαδρομή αυτή δεν έχει διακοπεί, τότε μπορείς να μεταβείς μεταξύ των δύο νησιών χωρίς να πληρώσεις, χρησιμοποιώντας τα αρχικά σου ανοιχτά εισιτήρια.

Εφόσον οι ανακοινώσεις της εταιρείας θα συμβαίνουν όσο ήδη ταξιδεύεις, θες να είσαι σε θέση να απαντάς γρήγορα σε ερωτήματα της μορφής: Με βάση τις παρούσες πληροφορίες, αν βρίσκομαι στο νησί \(i\) και έχω αρκετά χρήματα για \(k\) νέα εισιτήρια, ποιο είναι το πιο μακρινό νησί στο οποίο μπορώ να φτάσω;

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες Pascal, C, C++, Java το οποίο θα βοηθήσει στον σχεδιασμό του ταξιδιού σας. Το πρόγραμμά σας θα διαβάζει τις ανακοινώσεις της “Φθηνές αναξιόπιστες Lines” και τα δικά σας ερωτήματα, και για κάθε ερώτημα θα εκτυπώνει το πιο μακρινό νησί στο οποίο μπορείτε να φτάσετε βάσει των περιορισμών.

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

Το αρχείο εισόδου με όνομα islands.in είναι αρχείο κειμένου με την εξής δομή. Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς, χωρισμένους μεταξύ τους με ένα κενό διάστημα: το πλήθος των νησιών \(N\) και το πλήθος \(Q\) των ανακοινώσεων/ερωτημάτων σε χρονολογική σειρά. Στη συνέχεια ακολουθούν οι περιγραφές των \(Q\) ανακοινώσεων/ερωτημάτων. Πιο συγκεκριμένα, κάθε γραμμή περιέχει ένα χαρακτήρα \(T\), και δύο ακέραιους \(a\) και \(b\).

Αν ο χαρακτήρας είναι το γράμμα “D”, τότε η εταιρεία ανακοινώνει ότι παύει να πραγματοποιεί δρομολόγια μεταξύ όλων των ζευγών νησιών \((i, i+1)\), για κάθε \(a \leq i \leq b\).

Αν ο χαρακτήρας είναι το γράμμα “B”, τότε η εταιρεία ανακοινώνει ότι πραγματοποιεί τα δρομολόγια μεταξύ όλων των ζευγών νησιών \((i, i+1)\), για κάθε \(a \leq i \leq b\). Πιθανώς κάποια από αυτά τα δρομολόγια να λειτουργούσαν ήδη.

Αν ο χαρακτήρας είναι το γράμμα “Q”, τότε ρωτάς το πρόγραμμα ποιο είναι το πιο μακρινό νησί που μπορείς να φτάσεις αν ξεκινήσεις από το νησί \(a\) και έχεις αρκετά χρήματα για \(b\) εισιτήρια.

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

Το αρχείο εξόδου με όνομα islands.out είναι αρχείο κειμένου με την εξής δομή. Θα πρέπει να περιέχει μία γραμμή για κάθε ερώτημα (δηλαδή γράμμα “Q”), κατά σειρά. Η γραμμή αυτή περιέχει έναν ακέραιο μεταξύ \(1\) και \(N\), την απάντηση στο αντίστοιχο ερώτημα.

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

islands.in	islands.out
8 5 Q 3 0 D 3 6 Q 2 2 B 4 5 Q 2 2	8 5 8

Εξήγηση: Έχουμε \(N=8\) νησιά, και \(Q=5\) ανακοινώσεις/ερωτήματα.
Αρχικά έχουμε το ερώτημα: Αν βρίσκομαι στο νησί \(a=3\) και διαθέτω λεφτά για \(b=0\) εισιτήρια, πού μπορώ να φτάσω; Η απάντηση είναι \(8\), διότι δεν έχει διακοπεί ακόμα κανένα δρομολόγιο, κι επομένως μπορώ να φτάσω ως το τελευταίο νησί.

Ακολουθεί ανακοίνωση ότι δεν πραγματοποιούνται τα δρομολόγια από το νησί \(3\) μέχρι και το νησί \(6\), δηλαδή μεταξύ των νησιών \((3,4), (4,5), (5,6)\).

Ακολουθεί το ερώτημα: Αν βρίσκομαι στο νησί \(a=2\) και διαθέτω λεφτά για \(b=2\) νέα εισιτήρια, πού μπορώ να φτάσω; Η απάντηση είναι \(5\), διότι δεν πληρώνω για να πάω από το \(2\) στο \(3\), και πληρώνω για να πάω στο \(4\) και κατόπιν στο \(5\). Δεν μπορώ να συνεχίσω γιατί θα έπρεπε να πληρώσω ξανά για να πάω στο \(6\).

Ακολουθεί ανακοίνωση ότι πλέον πραγματοποιείται το δρομολόγιο \((4,5)\). Συνεπώς τα μόνα δρομολόγια που δεν πραγματοποιούνται τώρα είναι τα \((3,4)\) και \((5,6)\).

Ακολουθεί το ερώτημα: Αν βρίσκομαι στο νησί \(a=2\) και διαθέτω λεφτά για \(b=2\) εισιτήρια, πού μπορώ να φτάσω; Τώρα η απάντηση είναι \(8\), δεν πληρώνω για να πάω από το \(2\) στο \(3\), πληρώνω για να πάω στο \(4\), δεν πληρώνω για να πάω στο \(5\), πληρώνω για να πάω στο \(6\), και μετά δεν πληρώνω για να πάω στο \(7\) και το \(8\).

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

• \(1 \leq N \leq 500.000\) και \(1 \leq Q \leq 500.000\)
  
• Για κάθε ανακοίνωση \((a_i,b_i)\) θα είναι \(1 \leq a_i < b_i \leq N\)
  
• Για κάθε ερώτημα \((a_i,b_i)\) θα είναι \(1 \leq a_i \leq N\) και \(0 \leq b_i < N\)
  
• Για περιπτώσεις ελέγχου συνολικής αξίας 10% θα είναι \(N, Q \leq 1.000\).
  
• Για περιπτώσεις ελέγχου συνολικής αξίας 20% καμμία ανακοίνωση δε θα δίνεται μετά από ερώτημα.
  
• Για περιπτώσεις ελέγχου συνολικής αξίας 30% κάθε ανακοίνωση \((a_i,b_i)\) θα έχει \(b_i=a_i+1\).
  

Προσοχή:

Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

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