Σύγκριση φυτών (plants)

Ο Hazel ο βοτανολόγος επισκέφτηκε μια έκθεση στον Βοτανικό Κήπο της Σιγκαπούρης. Σε αυτή την έκθεση, φυτά με διακριτά ύψη τοποθετούνται σε κύκλο. Τα φυτά είναι αριθμημένα από το ~0~ μέχρι το ~n - 1~ δεξιόστροφα, με το φυτό ~n - 1~ να είναι δίπλα στο φυτό ~0~.

Για κάθε φυτό ~i~ (~0 \le i \le n - 1~), ο Hazel συγκρίνει το φυτό ~i~ με κάθε ένα από τα επόμενα ~k - 1~ φυτά δεξιόστροφα και καταγράφει τον αριθμό ~r[i]~ που δηλώνει πόσα από αυτά τα ~k - 1~ φυτά είναι ψηλότερα από το φυτό ~i~. Επομένως, η τιμή του ~r[i]~ εξαρτάται από τα σχετικά ύψη κάποιων ~k~ διαδοχικών φυτών.

Για παράδειγμα, έστω ότι ~n =5~, ~k = 3~ και ~i = 3~. Τα επόμενα ~k -1 = 2~ φυτά δεξιόστροφα από το φυτό ~i = 3~ είναι το φυτό ~4~ και το φυτό ~0~. Αν το φυτό ~4~ είναι ψηλότερο από το φυτό ~3~ και το φυτό ~0~ κοντύτερο από το φυτό ~3~, ο Hazel πρέπει να καταγράψει ~r[3] = 1~.

Μπορείτε να υποθέσετε ότι η Hazel έχει καταγράψει σωστά τις τιμές των ~r[i]~. Επομένως, υπάρχει τουλάχιστον μία διάταξη διακριτών υψών των φυτών που να είναι συνεπής με αυτές τις τιμές.

Σας ανατέθηκε να συγκρίνετε τα ύψη για ~q~ ζεύγη φυτών. Δυστυχώς, δεν έχετε πρόσβαση στην έκθεση. Η μόνη πηγή πληροφοριών σας είναι το σημειωματάριο του Hazel με την τιμή ~k~ και την ακολουθία τιμών ~r[0]~, ..., ~r[n - 1]~.

Για κάθε ζεύγος διαφορετικών φυτών ~x~ και ~y~ που πρέπει να συγκριθούν, προσδιορίστε ποια από τις τρεις ακόλουθες καταστάσεις συμβαίνει:

• Το φυτό ~x~ είναι σίγουρα ψηλότερο από το φυτό ~y~: σε οποιαδήποτε διάταξη διακριτών υψών ~h[0]~, ..., ~h[n - 1]~ που είναι συνεπής με τον πίνακα , ισχύει ~h[x] > h[y]~.
• Το φυτό ~x~ είναι σίγουρα κοντύτερο από το φυτό ~y~: σε οποιαδήποτε διάταξη διακριτών υψών ~h[0]~, ..., ~h[n - 1]~ που είναι συνεπής με τον πίνακα , ισχύει ~h[x] < h[y]~.
• Δε γνωρίζουμε με βεβαιότητα το αποτέλεσμα της σύγκρισης: δεν ισχύει καμία από τις δύο προηγούμενες περιπτώσεις.

Λεπτομέρειες Υλοποίησης

Πρέπει να υλοποιήσετε τις παρακάτω συναρτήσεις:

void init(int k, int[] r)

• ~k~:το πλήθος των διαδοχικών φυτών των οποίων το ύψος καθορίζει κάθε μεμονωμένη τιμή ~r[i]~.
• ~r~: ένας πίνακας μήκους ~n~, όπου ~r[i]~ είναι το πλήθος των φυτών που είναι ψηλότερα από το φυτό ~i~ ανάμεσα στα επόμενα ~k - 1~ φυτά, δεξιόστροφα.
• Αυτή η συνάρτηση καλείται μόνο μία φορά, πριν από οποιαδήποτε κλήση της compare_plants.

int compare_plants(int x, int y)

• ~x~, ~y~: οι αριθμοί των φυτών που θα συγκριθούν.
• Αυτή η συνάρτηση πρέπει να επιστρέφει:
  • 1 αν το φυτό ~x~ είναι σίγουρα ψηλότερο από το φυτό ~y~,
  • -1 αν το φυτό ~x~ είναι σίγουρα κοντύτερο από το φυτό ~y~,
  • 0 αν δε γνωρίζουμε με βεβαιότητα το αποτέλεσμα της σύγκρισης.
• Αυτή η συνάρτηση καλείται ακριβώς ~q~ φορές.

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

Παράδειγμα 1

Θεωρήστε την ακόλουθη κλήση:

init(3, [0, 1, 1, 2])

Έστω ότι ο βαθμολογητής καλεί την compare_plants(0, 2). Αφού ~r[0] = 0~, γνωρίζουμε ότι το φυτό ~2~ δεν είναι ψηλότερο από το φυτό ~0~. Επομένως, η κλήση πρέπει να επιστρέψει 1.

Έστω ότι ο βαθμολογητής καλεί την compare_plants(1, 2) μετά. Για όλες τις πιθανές διατάξεις υψών που είναι συνεπείς με τους παραπάνω περιορισμούς, το φυτό ~1~ είναι κοντύτερο από το φυτό ~2~. Επομένως, η κλήση πρέπει να επιστρέψει -1.

Παράδειγμα 2

Θεωρήστε την ακόλουθη κλήση:

init(2, [0, 1, 0, 1])

Έστω ότι ο βαθμολογητής καλεί την compare_plants(0, 3). Αφού ~r[3] = 1~, γνωρίζουμε ότι το φυτό ~0~ είναι ψηλότερο από το φυτό ~3~. Επομένως, η κλήση πρέπει να επιστρέψει 1.

Έστω ότι ο βαθμολογητής μετά καλεί την compare_plants(1, 3). Δύο διατάξεις υψών ~[3, 1, 4, 2]~ και ~[3, 2, 4, 1]~ είναι συνεπείς με τις μετρήσεις του Hazel. Εφόσον το φυτό ~1~ είναι κοντύτερο από το φυτό ~3~ στη μια διάταξη και ψηλότερο στην άλλη, η κλήση πρέπει επιστρέψει 0.

Περιορισμοί

• ~2 \le k \le n \le 200\,000~
• ~1 \le q \le 200\,000~
• ~0 \le r[i] \le k-1~ (για κάθε ~0 \le i \le n - 1~)
• Υπάρχει τουλάχιστον μία διάταξη διακριτών υψών των φυτών που να είναι συνεπής με τον πίνακα ~r~.

Υποπροβλήματα

1. (~5~ βαθμοί) ~k = 2~
2. (~14~ βαθμοί) ~n \le 5\,000, 2 \cdot k > n~
3. (~13~ βαθμοί) ~2 \cdot k > n~
4. (~17~ βαθμοί) Η σωστή απάντηση για κάθε κλήση της compare_plants είναι ~1~ ή ~- 1~.
5. (~11~ βαθμοί) ~n \le 300, q \le n\cdot(n-1) / 2~
6. (~15~ βαθμοί) ~x = 0~ για κάθε κλήση της compare_plants.
7. (~25~ βαθμοί) Κανένας επιπλέον περιορισμός.

Υπόδειγμα βαθμολογητή

Το υπόδειγμα βαθμολογητή διαβάζει την είσοδο στην εξής μορφή:

• γραμμή 1: ~n~ ~k~ ~q~
• γραμμή 2: ~r[0]~ ~r[1] ... r[n - 1]~
• γραμμή 3 + ~i~(~0 \le i \le q -1~): για την ~i~-οστή κλήση της compare_plants

Το υπόδειγμα βαθμολογητή τυπώνει τις απαντήσεις σας στην εξής μορφή:

• γραμμή 1 + ~i~(~0 \le i \le q -1~): η τιμή που επιστρέφει η ~i~-οστή κλήση της compare_plants.