Submission #9107531

---

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) :silent t)
  #-swank (set-dispatch-macro-character
           ;; enclose the form with VALUES to avoid being captured by LOOP macro
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(defmacro with-buffered-stdout (&body body)
  "Buffers all outputs to *STANDARD-OUTPUT* in BODY and flushes them to
*STANDARD-OUTPUT* after BODY has been done (without error). Note that only
BASE-CHAR is allowed."
  (let ((out (gensym)))
    `(let ((,out (make-string-output-stream :element-type 'base-char)))
       (let ((*standard-output* ,out))
         ,@body)
       (write-string (get-output-stream-string ,out)))))

;;;
;;; 2D range tree on an arbitrary commutative monoid
;;;
;;; build: O(nlog^2(n))
;;; query: O(log^2(n))
;;;
;;; Reference:
;;; https://www.cse.wustl.edu/~taoju/cse546/lectures/Lecture21_rangequery_2d.pdf
;;;

;; TODO: map all the points in a given rectangle
;; TODO: k-dimensional range tree

(declaim (inline op))
(defun op (a b)
  "Is a binary operator comprising a commutative monoid"
  (declare (fixnum a b))
  (min a b))

(defconstant +op-identity+ most-positive-fixnum
  "identity element w.r.t. OP")

(defstruct (xnode (:constructor make-xnode (xkey ynode left right))
                  (:conc-name %xnode-)
                  (:copier nil))
  (xkey 0 :type fixnum)
  ynode
  left right)

(defstruct (ynode (:constructor make-ynode (xkey ykey left right &key (count 1) value accumulator))
                  (:conc-name %ynode-)
                  (:copier nil))
  (xkey 0 :type fixnum)
  (ykey 0 :type fixnum)
  left
  right
  (count 1 :type (integer 0 #.most-positive-fixnum))
  (value +op-identity+ :type fixnum)
  (accumulator +op-identity+ :type fixnum))

(declaim (inline ynode-count))
(defun ynode-count (ynode)
  "Returns the number of the elements."
  (if (null ynode)
      0
      (%ynode-count ynode)))

(declaim (inline ynode-accumulator))
(defun ynode-accumulator (ynode)
  (if (null ynode)
      +op-identity+
      (%ynode-accumulator ynode)))

(declaim (inline ynode-update-count))
(defun ynode-update-count (ynode)
  (setf (%ynode-count ynode)
        (+ 1
           (ynode-count (%ynode-left ynode))
           (ynode-count (%ynode-right ynode)))))

(declaim (inline ynode-update-accumulator))
(defun ynode-update-accumulator (ynode)
  (setf (%ynode-accumulator ynode)
        (op (op (ynode-accumulator (%ynode-left ynode))
                (%ynode-value ynode))
            (ynode-accumulator (%ynode-right ynode)))))

(declaim (inline force-up))
(defun force-up (ynode)
  "Propagates the information up from children."
  (ynode-update-count ynode)
  (ynode-update-accumulator ynode))

;;
;; Merging w.r.t. Y-axis in O(n) time:
;; 1. transform two trees to two paths (with copying);
;; 2. merge the two paths into a path (destructively);
;; 3. transform the path to a tree (destructively);
;;

(declaim (inline %ynode-to-path))
(defun %ynode-to-path (ynode)
  "Returns a path that is equivalent to YNODE but in reverse order."
  (declare (inline make-ynode))
  (let ((res nil))
    (labels ((recur (node)
               (when node
                 (recur (%ynode-left node))
                 (setq res (make-ynode (%ynode-xkey node) (%ynode-ykey node) nil res
                                       :value (%ynode-value node)
                                       :accumulator (%ynode-value node)))
                 (recur (%ynode-right node)))))
      (recur ynode)
      res)))

(declaim (inline %ynode-merge-path!))
(defun %ynode-merge-path! (ypath1 ypath2)
  "Destructively merges two pathes in reverse order."
  (let ((res nil))
    (macrolet ((%push (y)
                 `(let ((rest (%ynode-right ,y)))
                    (setf (%ynode-right ,y) res
                          res ,y
                          ,y rest))))
      (loop (unless ypath1
              (loop while ypath2 do (%push ypath2))
              (return))
            (unless ypath2
              (loop while ypath1 do (%push ypath1))
              (return))
            ;; I use only #'< here for abstraction in the future
            (if (or (< (%ynode-ykey ypath1) (%ynode-ykey ypath2))
                    (and (not (< (%ynode-ykey ypath2) (%ynode-ykey ypath1)))
                         (< (%ynode-xkey ypath1) (%ynode-xkey ypath2))))
                (%push ypath2)
                (%push ypath1)))
      res)))

(declaim (inline %path-to-ynode!))
(defun %path-to-ynode! (ypath length)
  "Destructively transforms a path to a balanced binary tree."
  (declare ((integer 0 #.most-positive-fixnum) length))
  (let* ((max-depth (- (integer-length length) 1)))
    (macrolet ((%pop ()
                 `(let ((rest (%ynode-right ypath))
                        (first ypath))
                    (setf (%ynode-right first) nil
                          ypath rest)
                    first)))
      (labels ((build (depth)
                 (declare ((integer 0 #.most-positive-fixnum) depth))
                 (when ypath
                   (if (= depth max-depth)
                       (%pop)
                       (let ((left (build (+ 1 depth))))
                         (if (null ypath)
                             left
                             (let* ((node (%pop))
                                    (right (build (+ 1 depth))))
                               (setf (%ynode-left node) left)
                               (setf (%ynode-right node) right)
                               (force-up node)
                               node)))))))
        (build 0)))))

(defun %ynode-merge (ynode1 ynode2)
  "Merges two YNODEs non-destructively in O(n)."
  (declare (optimize (speed 3) (safety 0)))
  (let* ((length (+ (ynode-count ynode1) (ynode-count ynode2))))
    (declare (fixnum length))
    (%path-to-ynode!
     (%ynode-merge-path! (%ynode-to-path ynode1)
                         (%ynode-to-path ynode2))
     length)))

(declaim (inline make-range-tree))
(defun make-range-tree (points &key (xkey #'car) (ykey #'cdr) value-key)
  "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)).

If VALUE-KEY is given, the i-th point is bounded to the value (FUNCALL VALUE-KEY
POINTS[i]), otherwise to the value +OP-IDENTITY+."
  (declare ((simple-array list (*)) points))
  (labels ((build (l r)
             (declare ((integer 0 #.most-positive-fixnum) l r))
             (if (= (- r l) 1)
                 (let* ((point (aref points l))
                        (x (funcall xkey point))
                        (y (funcall ykey point))
                        (value (if value-key (funcall value-key point) +op-identity+)))
                   (make-xnode x (make-ynode x y nil nil
                                             :value value
                                             :accumulator value)
                               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+ most-negative-fixnum)
(defconstant +pos-inf+ most-positive-fixnum)

(declaim (inline xleaf-p))
(defun xleaf-p (xnode)
  (and (null (%xnode-left xnode)) (null (%xnode-right xnode))))

;; Below is almost the same as RT-COUNT. Is it better to integrate them?
(defun rt-query (range-tree x1 y1 x2 y2)
  "Queries the `sum' of the nodes in the rectangle [x1, y1)*[x2, 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 fixnum) 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+))
  (labels ((xrecur (xnode x1 x2)
             (declare ((or null xnode) xnode)
                      (fixnum x1 x2)
                      ;; KLUDGE: declaring ftype is not sufficient for the
                      ;; optimization on SBCL 1.1.14.
                      #+sbcl (values (integer 0 #.most-positive-fixnum)))
             (cond ((null xnode) +op-identity+)
                   ((and (= x1 +neg-inf+) (= x2 +pos-inf+))
                    (yrecur (%xnode-ynode xnode) y1 y2))
                   (t
                    (let ((xkey (%xnode-xkey xnode)))
                      (if (<= x1 xkey)
                          (if (< xkey x2)
                              ;; XKEY is in [X1, X2)
                              (if (xleaf-p xnode)
                                  (yrecur (%xnode-ynode xnode) y1 y2)
                                  (op (xrecur (%xnode-left xnode) x1 +pos-inf+)
                                      (xrecur (%xnode-right xnode) +neg-inf+ x2)))
                              ;; XKEY is in [X2, +inf)
                              (xrecur (%xnode-left xnode) x1 x2))
                          ;; XKEY is in (-inf, X1)
                          (xrecur (%xnode-right xnode) x1 x2))))))
           (yrecur (ynode y1 y2)
             (declare ((or null ynode) ynode)
                      (fixnum y1 y2)
                      #+sbcl (values (integer 0 #.most-positive-fixnum)))
             (cond ((null ynode) +op-identity+)
                   ((and (= y1 +neg-inf+) (= y2 +pos-inf+))
                    (%ynode-accumulator ynode))
                   (t
                    (let ((key (%ynode-ykey ynode)))
                      (if (<= y1 key)
                          (if (< key y2)
                              (op (op (yrecur (%ynode-left ynode) y1 +pos-inf+)
                                      (%ynode-value ynode))
                                  (yrecur (%ynode-right ynode) +neg-inf+ y2))
                              (yrecur (%ynode-left ynode) y1 y2))
                          (yrecur (%ynode-right ynode) y1 y2)))))))
    ;; (declare (ftype (function * (values (integer 0 #.most-positive-fixnum) &optional)) xrecur yrecur))
    (xrecur range-tree x1 x2)))

(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)))

(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)

(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+ 1000000007)

;;;
;;; Body
;;;

(defun preprocess ()
  (let* ((n (read))
         (intervals (make-array n :element-type 'list))
         (dict (make-array n :element-type 'list))
         (end 0)
         (table (make-hash-table :size n :test #'equal)))
    (dotimes (index n)
      (let ((l (read-fixnum))
            (r (read-fixnum)))
        (unless (gethash (cons l r) table)
          (setf (gethash (cons l r) table) t
                (aref intervals end) (list* l r index)
                (aref dict index) (aref intervals end)
                end (+ end 1)))))
    (values end
            (adjust-array intervals end)
            dict)))

(defun main ()
  (declare #.OPT)
  (multiple-value-bind (n intervals dict) (preprocess)
    (declare ((simple-array list (*)) intervals dict)
             (uint32 n))
    (setq intervals (sort intervals #'> :key (lambda (x) (the uint32 (car x)))))
    (let ((schedule (make-array n :element-type 'list))
          (prev-l 1000000)
          (end 0))
      (loop for interval across intervals
            for (l r) of-type (uint32 uint32) = interval
            when (<= r prev-l)
            do (setf (aref schedule end) interval
                     end (+ end 1)
                     prev-l l))
      (println end)
      (setq intervals (sort intervals
                            (lambda (x y)
                              (or (< (the uint32 (first x))
                                     (the uint32 (first y)))
                                  (and (= (the uint32 (first x))
                                          (the uint32 (first y)))
                                       (< (the uint32 (second x))
                                          (the uint32 (second y))))))))
      (gc)
      (let ((schedule (nreverse (subseq schedule 0 end)))
            (rtree (make-range-tree intervals
                                    :xkey #'car
                                    :ykey #'cadr
                                    :value-key #'cddr))
            (prev-r 0)
            (init t))
        (labels ((write* (x)
                   (if init
                       (setq init nil)
                       (write-char #\ ))
                   (write x)))
          (with-buffered-stdout
            (loop for i from 1 below end
                  for (next-l next-r) = (aref schedule i)
                  for argmin = (rt-query rtree prev-r prev-r (+ 1 next-l) (+ 1 next-l))
                  for (min-l min-r) = (aref dict argmin)
                  do (write* (+ argmin 1))
                     (dbg min-l min-r argmin)
                     (setq prev-r min-r)
                  finally (let ((argmin (rt-query rtree prev-r prev-r nil nil)))
                            (write* (+ argmin 1))))
            (terpri)))))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    ;; (run-program "C:/Windows/System32/WindowsPowerShell/v1.0/powershell.exe" '("get-clipboard") :output out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "100000~%")
    (dotimes (i 100000)
      (let ((a (random 1000))
            (b (random 1000)))
        (when (> a b)
          (rotatef a b))
        (when (= a b)
          (incf b))
        (format out "~D ~D~%" a b)))))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "4
0 5
0 3
3 7
5 10
"
    "2
1 4
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "5
0 5
0 3
3 7
5 10
7 12
"
    "3
2 3 5
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "8
1 5
3 9
2 5
1 2
8 10
9 11
7 15
10 14
"
    "4
4 3 5 8
")))

Submission Info

Judge Result