Submission #9248691
Source Code Expand
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
(sb-int:defconstant-eqx OPT
#+swank '(optimize (speed 3) (safety 2))
#-swank '(optimize (speed 3) (safety 0) (debug 0))
#'equal)
#+swank (ql:quickload '(:cl-debug-print :fiveam))
#-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy
;; BEGIN_INSERTED_CONTENTS
(defmacro define-int-types (&rest bits)
`(progn
,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)
;;;
;;; 2D range tree with fractional cascading
;;;
;;; build: O(nlog(n))
;;; query: O(log(n))
;;;
;; TODO: map all the points in a given rectangle
;; TODO: introduce abelian group
(defstruct (ynode (:constructor make-ynode (xkeys ykeys lpointers rpointers))
(:conc-name %ynode-)
(:copier nil))
(xkeys nil :type (simple-array int32 (*)))
(ykeys nil :type (simple-array int32 (*)))
(lpointers nil :type (or null (simple-array uint31 (*))))
(rpointers nil :type (or null (simple-array uint31 (*)))))
(defstruct (xnode (:constructor make-xnode (xkey ynode left right))
(:conc-name %xnode-)
(:copier nil))
(xkey 0 :type int32)
(ynode nil :type ynode)
(left nil :type (or null xnode))
(right nil :type (or null xnode)))
(defun %ynode-merge (ynode1 ynode2)
"Merges two YNODEs non-destructively in O(n)."
(declare #.OPT)
(let* ((xkeys1 (%ynode-xkeys ynode1))
(ykeys1 (%ynode-ykeys ynode1))
(xkeys2 (%ynode-xkeys ynode2))
(ykeys2 (%ynode-ykeys ynode2))
(len1 (length xkeys1))
(len2 (length xkeys2))
(new-len (+ len1 len2))
(new-xkeys (make-array new-len :element-type 'int32))
(new-ykeys (make-array new-len :element-type 'int32))
(lpointers (make-array (+ 1 new-len)
:element-type 'uint31))
(rpointers (make-array (+ 1 new-len)
:element-type 'uint31))
(new-pos 0)
(pos1 0)
(pos2 0))
(declare (uint31 len1 len2 new-len new-pos pos1 pos2))
;; merge two vectors
(loop
(when (= pos1 len1)
(loop
for i from pos2 below len2
do (setf (aref new-xkeys new-pos) (aref xkeys2 i)
(aref new-ykeys new-pos) (aref ykeys2 i)
(aref lpointers new-pos) pos1
(aref rpointers new-pos) i)
(incf new-pos))
(return))
(when (= pos2 len2)
(loop
for i from pos1 below len1
do (setf (aref new-xkeys new-pos) (aref xkeys1 i)
(aref new-ykeys new-pos) (aref ykeys1 i)
(aref lpointers new-pos) i
(aref rpointers new-pos) pos2)
(incf new-pos))
(return))
(if (or (< (aref ykeys1 pos1) (aref ykeys2 pos2))
(and (= (aref ykeys1 pos1) (aref ykeys2 pos2))
(< (aref xkeys1 pos1) (aref xkeys2 pos2))))
(setf (aref new-xkeys new-pos) (aref xkeys1 pos1)
(aref new-ykeys new-pos) (aref ykeys1 pos1)
(aref lpointers new-pos) pos1
(aref rpointers new-pos) pos2
pos1 (+ pos1 1))
(setf (aref new-xkeys new-pos) (aref xkeys2 pos2)
(aref new-ykeys new-pos) (aref ykeys2 pos2)
(aref lpointers new-pos) pos1
(aref rpointers new-pos) pos2
pos2 (+ pos2 1)))
(incf new-pos))
(setf (aref lpointers new-len) len1
(aref rpointers new-len) len2)
(make-ynode new-xkeys new-ykeys lpointers rpointers)))
(declaim (inline make-range-tree))
(defun make-range-tree (points &key (xkey #'car) (ykey #'cdr))
"points := vector of poins
Makes a range tree from the points. These points must be sorted
w.r.t. lexicographical order and must not contain duplicate points. (Duplicate
coordinates are allowed.) E.g. (-1, 3), (-1, 4), (-1, 7) (0, 1) (0, 3) (2,
-1) (2, 1))."
(declare ((simple-array (cons int32 int32) (*)) points))
(when (zerop (length points))
(return-from make-range-tree nil))
(let ((pointers-for-leaf
(make-array 2
:element-type 'uint31
:initial-element 0)))
(labels
((build (l r)
(declare (uint31 l r))
(if (= (- r l) 1)
(let* ((point (aref points l))
(x (funcall xkey point))
(y (funcall ykey point))
(xkeys (make-array 1 :element-type 'int32))
(ykeys (make-array 1 :element-type 'int32)))
(setf (aref xkeys 0) x
(aref ykeys 0) y)
(make-xnode x (make-ynode xkeys ykeys
pointers-for-leaf
pointers-for-leaf)
nil nil))
(let* ((mid (ash (+ l r) -1))
(left (build l mid))
(right (build mid r)))
(make-xnode (funcall xkey (aref points mid))
(%ynode-merge (%xnode-ynode left)
(%xnode-ynode right))
left right)))))
(build 0 (length points)))))
(defconstant +neg-inf+ #x-80000000)
(defconstant +pos-inf+ #x7fffffff)
(declaim (inline xleaf-p))
(defun xleaf-p (xnode)
(and (null (%xnode-left xnode)) (null (%xnode-right xnode))))
(defun rt-count (range-tree x1 y1 x2 y2)
"Returns the number of the nodes within the rectangle [x1, x2)*[y1, y2). A
part or all of these coordinates can be NIL; then they are regarded as the
negative or positive infinity."
(declare #.OPT
((or null int32) x1 y1 x2 y2))
(setq x1 (or x1 +neg-inf+)
x2 (or x2 +pos-inf+)
y1 (or y1 +neg-inf+)
y2 (or y2 +pos-inf+))
(unless range-tree
(return-from rt-count 0))
(let* ((ynode (%xnode-ynode range-tree))
(xkeys (%ynode-xkeys ynode))
(ykeys (%ynode-ykeys ynode)))
(labels ((bisect-left (y)
(declare (int32 y))
(let ((left 0)
(ok (length xkeys)))
(declare (uint31 left ok))
(loop
(let ((mid (ash (+ left ok) -1)))
(if (= mid left)
(if (< (aref ykeys left) y)
(return ok)
(return left))
(if (< (aref ykeys mid) y)
(setq left mid)
(setq ok mid)))))))
(recur (xnode x1 x2 start end)
(declare ((or null xnode) xnode)
(int32 x1 x2)
;; KLUDGE: declaring ftype is not sufficient for the
;; optimization on SBCL 1.1.14.
#+sbcl (values uint31))
(cond ((null xnode) 0)
((and (= x1 +neg-inf+) (= x2 +pos-inf+))
(- end start))
(t
(let* ((xkey (%xnode-xkey xnode))
(ynode (%xnode-ynode xnode))
(lpointers (%ynode-lpointers ynode))
(rpointers (%ynode-rpointers ynode)))
(if (<= x1 xkey)
(if (< xkey x2)
;; XKEY is in [X1, X2)
(if (xleaf-p xnode)
(- end start)
(+ (recur (%xnode-left xnode)
x1 +pos-inf+
(aref lpointers start)
(aref lpointers end))
(recur (%xnode-right xnode)
+neg-inf+ x2
(aref rpointers start)
(aref rpointers end))))
;; XKEY is in [X2, +inf)
(recur (%xnode-left xnode)
x1 x2
(aref lpointers start)
(aref lpointers end)))
;; XKEY is in (-inf, X1)
(recur (%xnode-right xnode)
x1 x2
(aref rpointers start)
(aref rpointers end))))))))
(let ((start (bisect-left y1))
(end (bisect-left y2)))
(recur range-tree x1 x2 start end)))))
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
(declare #.OPT)
(macrolet ((%read-byte ()
`(the (unsigned-byte 8)
#+swank (char-code (read-char in nil #\Nul))
#-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
(let* ((minus nil)
(result (loop (let ((byte (%read-byte)))
(cond ((<= 48 byte 57)
(return (- byte 48)))
((zerop byte) ; #\Nul
(error "Read EOF or #\Nul."))
((= byte #.(char-code #\-))
(setf minus t)))))))
(declare ((integer 0 #.most-positive-fixnum) result))
(loop
(let* ((byte (%read-byte)))
(if (<= 48 byte 57)
(setq result (+ (- byte 48) (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result))))
(return (if minus (- result) result))))))))
(defmacro dbg (&rest forms)
#+swank
(if (= (length forms) 1)
`(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
`(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
#-swank (declare (ignore forms)))
(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
(let ((*read-default-float-format* 'double-float))
(prog1 (princ obj stream) (terpri stream))))
(defconstant +mod+ 998244353)
;; Body
;;;
;;; Arithmetic operations with static modulus
;;;
(defmacro define-mod-operations (&optional (divisor 1000000007))
`(progn
(defun mod* (&rest args)
(reduce (lambda (x y) (mod (* x y) ,divisor)) args))
(sb-c:define-source-transform mod* (&rest args)
(if (null args)
1
(reduce (lambda (x y) `(mod (* ,x ,y) ,',divisor)) args)))
(defun mod+ (&rest args)
(reduce (lambda (x y) (mod (+ x y) ,divisor)) args))
(sb-c:define-source-transform mod+ (&rest args)
(if (null args)
0
(reduce (lambda (x y) `(mod (+ ,x ,y) ,',divisor)) args)))
(define-modify-macro incfmod (delta divisor)
(lambda (x y divisor) (mod (+ x y) divisor)))
(define-modify-macro decfmod (delta divisor)
(lambda (x y divisor) (mod (- x y) divisor)))))
(define-mod-operations +mod+)
(defun main ()
(declare #.OPT
(inline sort)
(muffle-conditions style-warning))
(let* ((n (read))
(powers (make-array 200001 :element-type 'uint31))
(points (make-array n :element-type '(cons int32 int32)))
(res 0))
(declare (uint32 n)
(uint62 res)
((simple-array uint31 (*)) powers))
;; construct table of 2^n
(setf (aref powers 0) 1)
(loop for i from 1 below (length powers)
do (setf (aref powers i)
(mod* 2 (aref powers (- i 1)))))
(dotimes (i n)
(setf (aref points i) (cons (read-fixnum) (read-fixnum))))
(setq points
(sort points #'< :key (lambda (x) (the int32 (car x)))))
(let ((rtree (make-range-tree points)))
;; L R U D
(incfmod res (mod* (- n 4) (- (aref powers n) 1)) +mod+)
;; LU LD RU RD
(dotimes (i n)
(let* ((point (aref points i))
(x (car point))
(y (cdr point))
(ld (rt-count rtree nil nil x y))
(lu (rt-count rtree nil (+ y 1) x nil))
(rd (rt-count rtree (+ x 1) (+ y 1) nil nil))
(ru (rt-count rtree (+ x 1) nil nil y)))
(declare (int32 x y))
(incf res (+ (aref powers ld) (aref powers lu) (aref powers rd) (aref powers ru))))))
(println (mod res +mod+))))
#-swank (main)
Submission Info
| Submission Time |
|
| Task |
F - Enclosed Points |
| User |
sansaqua |
| Language |
Common Lisp (SBCL 1.1.14) |
| Score |
600 |
| Code Size |
13348 Byte |
| Status |
AC |
| Exec Time |
908 ms |
| Memory |
244584 KiB |
Judge Result
| Set Name |
Sample |
All |
| Score / Max Score |
0 / 0 |
600 / 600 |
| Status |
|
|
| Set Name |
Test Cases |
| Sample |
s1.txt, s2.txt, s3.txt |
| All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, s1.txt, s2.txt, s3.txt |
| Case Name |
Status |
Exec Time |
Memory |
| 01.txt |
AC |
364 ms |
51040 KiB |
| 02.txt |
AC |
191 ms |
37604 KiB |
| 03.txt |
AC |
189 ms |
37604 KiB |
| 04.txt |
AC |
190 ms |
37604 KiB |
| 05.txt |
AC |
190 ms |
37604 KiB |
| 06.txt |
AC |
189 ms |
37604 KiB |
| 07.txt |
AC |
189 ms |
37608 KiB |
| 08.txt |
AC |
190 ms |
37600 KiB |
| 09.txt |
AC |
190 ms |
37604 KiB |
| 10.txt |
AC |
189 ms |
37604 KiB |
| 11.txt |
AC |
894 ms |
242656 KiB |
| 12.txt |
AC |
804 ms |
140136 KiB |
| 13.txt |
AC |
896 ms |
244580 KiB |
| 14.txt |
AC |
803 ms |
140128 KiB |
| 15.txt |
AC |
908 ms |
244580 KiB |
| 16.txt |
AC |
907 ms |
244584 KiB |
| 17.txt |
AC |
908 ms |
244580 KiB |
| 18.txt |
AC |
908 ms |
244576 KiB |
| 19.txt |
AC |
832 ms |
244576 KiB |
| 20.txt |
AC |
739 ms |
142176 KiB |
| 21.txt |
AC |
843 ms |
244580 KiB |
| 22.txt |
AC |
847 ms |
244580 KiB |
| 23.txt |
AC |
189 ms |
37608 KiB |
| s1.txt |
AC |
190 ms |
37604 KiB |
| s2.txt |
AC |
190 ms |
37608 KiB |
| s3.txt |
AC |
189 ms |
37604 KiB |