38ος ΠΔΠ Γ' Φάση
Ταμπλέτα ζωγραφικής (flips)
[ Μονάδες]
Ο μικρός ανιψιός του Τάκη, ο Λάζαρος, έχει μία παράξενη ταμπλέτα ζωγραφικής. Η ταμπλέτα μπορεί να αναπαρασταθεί ως ένα πλέγμα διαστάσεων \(N \times N\), δηλαδή ένα πλέγμα με \(N\) γραμμές και \(N\) στήλες. Κάθε κελί του πλέγματος μπορεί να είναι είτε λευκό, είτε μαύρο. Αρχικά, \(K\) κελιά είναι μαύρα και τα υπόλοιπα είναι λευκά.
Ο Λάζαρος ξέρει να χρησιμοποιεί μόνο ένα εργαλείο της ταμπλέτας, το οποίο δέχεται τέσσερις αριθμούς \(a\), \(b\), \(c\), \(d\), βρίσκει όλα τα κελιά \((x, y)\) για τα οποία ισχύει \(a \leq x \leq b\) και \(c \leq y \leq d\) και αντιστρέφει ταυτόχρονα το χρώμα τους. Όταν λέμε ότι αντιστρέφουμε το χρώμα ενός κελιού, εννοούμε ότι αν είναι λευκό τού αλλάζουμε το χρώμα σε μαύρο, ενώ αν είναι μαύρο τού αλλάζουμε το χρώμα σε λευκό. Ο Λάζαρος θα κάνει αλλαγές στην ταμπλέτα Q φορές, χρησιμοποιώντας αυτό το εργαλείο.
Αντίθετα, ο Τάκης ξέρει να χρησιμοποιεί μόνο ένα άλλο εργαλείο. Αυτό το εργαλείο του επιτρέπει να διαλέγει οποιαδήποτε γραμμή ή στήλη θέλει και να αντιστρέφει το χρώμα όλων των κελιών της ταυτόχρονα.
Θα ορίσουμε ως “αντιστρεψιμότητα” της ταμπλέτας το πλήθος των τρόπων με τους οποίους ο Τάκης μπορεί να κάνει όλα τα κελιά της ταμπλέτας λευκά, ταυτόχρονα, χρησιμοποιώντας το εργαλείο του το πολύ μία φορά σε κάθε γραμμή και στήλη. Ενδέχεται ο Τάκης να μην μπορεί με κανέναν τρόπο να κάνει όλα τα κελιά της ταμπλέτας λευκά ταυτόχρονα, και σε αυτή την περίπτωση θεωρούμε ότι η αντιστρεψιμότητα είναι \(0\).
Ο Τάκης θέλει να γνωρίζει την αντιστρεψιμότητα της ταμπλέτας, πριν ο Λάζαρος αρχίσει να την αλλάζει, καθώς και μετά από κάθε αλλαγή.
Δεδομένα εισόδου (stdin)
Η πρώτη γραμμή περιέχει τρεις ακέραιους αριθμούς \(N\), \(K\), \(Q\): την διάσταση της ταμπλέτας, το πλήθος των κελιών που είναι αρχικά μαύρα και το πλήθος των αλλαγών που θα ακολουθήσουν.
Ακολουθούν \(K\) γραμμές, καθεμία από τις οποίες περιέχει δύο ακέραιους αριθμούς \(x_i\) και \(y_i\): τις συντεταγμένες των κελιών που είναι αρχικά μαύρα. Ακολουθούν \(Q\) γραμμές, καθεμία από τις οποίες περιέχει τέσσερις ακέραιους αριθμούς \(a_i\), \(b_i\), \(c_i\), \(d_i\): τις περιγραφές των αλλαγών του Λάζαρου.
Δεδομένα εξόδου (stdout)
Πρέπει να αποτελείται από \(Q+1\) γραμμές. Η πρώτη γραμμή πρέπει να περιέχει την αντιστρεψιμότητα της ταμπλέτας πριν από τις αλλαγές του Λάζαρου. Καθεμία από τις επόμενες \(Q\) γραμμές πρέπει να περιέχει την αντιστρεψιμότητα της ταμπλέτας ακριβώς μετά την αντίστοιχη αλλαγή του Λάζαρου.
Παράδειγμα εισόδου-εξόδου
| stdin | stdout |
|---|---|
| 3 2 1 1 1 2 1 3 3 2 3 |
0 2 |
Εξήγηση παραδείγματος: Αρχικά, μόνο τα κελιά \((1, 1)\) και \((2, 1)\) είναι μαύρα και μπορεί να αποδειχθεί ότι δεν υπάρχει τρόπος ο Τάκης να κάνει όλα τα κελιά λευκά χρησιμοποιώντας το εργαλείο του, άρα η αντιστρεψιμότητα της ταμπλέτας είναι \(0\). Στη συνέχεια, ο Λάζαρος αντιστρέφει το χρώμα των κελιών \((3,2)\) και \((3,3)\), από λευκά σε μαύρα. Πλέον, υπάρχουν δύο τρόποι ο Τάκης να πετύχει τον στόχο του (για παράδειγμα, ένας είναι χρησιμοποιώντας το εργαλείο μία φορά στην πρώτη στήλη και μία φορά στην τρίτη γραμμή), άρα η αντιστρεψιμότητα της ταμπλέτας είναι \(2\).
Περιορισμοί
- \(1 \leq N \leq 10^9\).
- \(0 \leq K, Q \leq 200.000\).
- \(1 \leq x_i , y_i \leq N\).
- Τα \(K\) μαύρα κελιά που δίνονται είναι διαφορετικά μεταξύ τους.
- \(1 \leq a_i \leq b_i \leq N\).
- \(1 \leq c_i \leq d_i \leq N\).
Υποπροβλήματα
- (8 βαθμοί) \(N \leq 9, Q = 0\).
- (18 βαθμοί) \(N \leq 1.000\), \(Q = 0\).
- (19 βαθμοί) \(N \leq 1.000\), \(Q \leq 10.000\), \(a_i = b_i\) και \(c_i = d_i\), για κάθε \(i\) (\(1 \leq i \leq Q\))
- (13 βαθμοί) \(N \leq 1.000\), \(Q \leq 10.000\).
- (20 βαθμοί) \(a_i = b_i\) και \(c_i = d_i\), για κάθε \(i\) (\(1 \leq i \leq Q\)).
- (22 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.
Παρατηρήσεις
Μέγιστος χρόνος εκτέλεσης: \(1.5\) sec.
Μέγιστη διαθέσιμη μνήμη: \(128\) MB.