Περπάτημα στον αέρα

Ο Κενάν έφτιαξε ένα σχέδιο με τα κτήρια και τις γέφυρες (skywalks) που βρίσκονται κατά μήκος της μίας πλευράς της κύριας λεωφόρου του Μπακού. Υπάρχουν ~n~ κτήρια αριθμημένα από ~0~ μέχρι ~n - 1~ και ~m~ γέφυρες αριθμημένες από ~0~ μέχρι ~m - 1~. Τα κτήρια και οι γέφυρες είναι σχεδιασμένα στο διδιάστατο επίπεδο ως κατακόρυφα και οριζόντια ευθύγραμμα τμήματα αντίστοιχα.

Η βάση του κτηρίου ~i~ (~0 \le i \le n - 1~) βρίσκεται στο σημείο (~x[i], 0~) και το κτήριο έχει ύψος ~h[i]~. Έτσι, το κτήριο σχεδιάζεται ως ένα κατακόρυφο ευθύγραμμο τμήμα που ενώνει τα σημεία (~x[i], 0~) και (~x[i], h[i]~).

Η γέφυρα ~j~ (~0 \le j \le m - 1~) έχει άκρα στα κτήρια με αριθμούς ~l[j]~ και ~r[j]~ και έχει μια θετική συντεταγμένη ~y = y[j]~. Έτσι, η γέφυρα σχεδιάζεται ως ένα οριζόντιο ευθύγραμμο τμήμα που ενώνει τα σημεία (~x[l[j]], y[j]~) και (~x[r[j]], y[j]~).

Μια γέφυρα και ένα κτήριο τέμνονται αν έχουν κοινό σημείο. Έτσι, μια γέφυρα τέμνει τα δυο κτήρια που βρίσκονται στα άκρα της, μπορεί όμως να τέμνει και άλλα κτήρια ενδιάμεσα.

Ο Κενάν θέλει να βρει το μήκος της μικρότερης διαδρομής από τη βάση του κτηρίου ~s~ στη βάση του κτηρίου ~g~, υποθέτοντας ότι μπορεί να περπατήσει μόνο κατά μήκος των κτηρίων και των γεφυρών, ή να αποφασίσει ότι δεν υπάρχει τέτοια διαδρομή. Σημειώστε ότι δεν επιτρέπεται να περπατήσει στο έδαφος, δηλαδή στην οριζόντια γραμμή με συντεταγμένη ~y = 0~.

Μπορεί να περπατήσει από μια γέφυρα σε ένα κτήριο και αντίστροφα, σε κάθε σημείο που αυτά τέμνονται. Αν τα άκρα δυο γεφυρών βρίσκονται στο ίδιο σημείο, μπορεί να περπατήσει από τη μια γέφυρα στην άλλη. Βοηθήστε τον Κενάν να λύσει αυτό το πρόβλημα.

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

Θα πρέπει να υλοποιήσετε την ακόλουθη συνάρτηση. Θα κληθεί από τον βαθμολογητή μία φορά για κάθε test case.

int64 min_distance(int[] x, int[] h, int[] l, int[] r, int[] y,
                   int s, int g)

• ~x~ και ~h~: πίνακες ακέραιων αριθμών μήκους ~n~, οι συντεταγμένες ~x~ και τα ύψη των κτηρίων
• ~l~, ~r~, και ~y~: πίνακες ακέραιων αριθμών μήκους ~m~, οι αριθμοί των κτηρίων που βρίσκονται στα άκρα και οι συντεταγμένες ~y~ των γεφυρών
• ~s~ και ~g~: δύο ακέραιοι αριθμοί, το αρχικό και το τελικό κτήριο
• Αυτή η συνάρτηση πρέπει να επιστρέφει το μήκος της ελάχιστης διαδρομής μεταξύ της βάσης του κτηρίου ~s~ και της βάσης του κτηρίου ~g~, αν υπάρχει τέτοια διαδρομή. Διαφορετικά πρέπει να επιστρέφει -1.

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

Παράδειγμα 1

Θεωρήστε την επόμενη κλήση της συνάρτησης:

min_distance([0, 3, 5, 7, 10, 12, 14],
             [8, 7, 9, 7, 6, 6, 9],
             [0, 0, 0, 2, 2, 3, 4],
             [1, 2, 6, 3, 6, 4, 6],
             [1, 6, 8, 1, 7, 2, 5],
             1, 5)

Η σωστή απάντηση είναι ~27~.

Η παρακάτω εικόνα αντιστοιχεί στο Παράδειγμα 1.

Παράδειγμα 2

min_distance([0, 4, 5, 6, 9],
             [6, 6, 6, 6, 6],
             [3, 1, 0],
             [4, 3, 2],
             [1, 3, 6],
             0, 4)

Η σωστή απάντηση είναι ~21~.

Περιορισμοί

• ~1\ le n, m \le 100\,000~
• ~0 \le x[0] < x[1] < ... < x[n - 1] \le 10^9~
• ~1 \le h[i] \le 10^9~ (για κάθε ~0 \le i \le n - 1~)
• ~0 \le l[j] < r[j] \le n - 1~ (για κάθε ~0 \le j \le m - 1~)
• ~1 \le y[j] \le min(h[l[j]], h[r[j]])~ (για κάθε ~0 \le j \le m - 1~)
• ~s \ne g~
• Καμία γέφυρα δεν έχει κοινά σημεία με καμία άλλη γέφυρα, εκτός ίσως από τα άκρα των δύο γεφυρών.

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

1. (~10~ βαθμοί) ~n, m \le 50~
2. (~14~ βαθμοί) Κάθε γέφυρα τέμνει το πολύ ~10~ κτήρια.
3. (~15~ βαθμοί) ~s = 0~, ~g = n - 1~ και όλα τα κτήρια έχουν το ίδιο ύψος.
4. (~18~ βαθμοί) ~s = 0~, ~g = n - 1~
5. (~43~ βαθμοί) Κανένας επιπλέoν περιορισμός.

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

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

• γραμμή ~1~: ~n~ ~m~
• γραμμή ~2 + i~ (~0 \le i \le n - 1~): ~x[i]~ ~h[i]~
• γραμμή ~n + 2 + j~ (~0 \le j \le m - 1~): ~l[j]~ ~r[j]~ ~y[j]~
• γραμμή ~n + m + 2~: ~s~ ~g~

Ο υποδειγματικός βαθμολογητής τυπώνει μία γραμμή που περιέχει την τιμή που επιστρέφει η συνάρτηση min_distance.