提出 #4553846

---

ソースコード 拡げる

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (terminate-char #\Space))
  "Note that the returned string will be reused."
  (let ((buffer (gensym))
        (character (gensym))
        (idx (gensym)))
    `(let ((,buffer (load-time-value (make-string ,buffer-size
                                                  :element-type 'base-char))))
       (declare (simple-base-string ,buffer))
       (loop for ,character of-type base-char =
                #-swank (code-char (read-byte ,in nil #.(char-code #\Newline)))
                #+swank (read-char ,in nil #\Newline)
             for ,idx from 0
             until (char= ,character #\Newline)
             do (setf (schar ,buffer ,idx) ,character)
             finally (when (< ,idx ,buffer-size)
                       (setf (schar ,buffer ,idx) ,terminate-char))
                     (return (values ,buffer ,idx))))))

(defmacro split-objs-bind (vars string &body body)
  (let ((position (gensym))
        (s (gensym)))
    (labels ((expand (vars &optional init-pos)
               (if (null vars)
                   body
                   (let ((var (if (listp (car vars)) (car vars) (list (car vars)))))
                     `((multiple-value-bind (,(car var) ,position)
                           ,(if (second var)
                                `(funcall ,(second var) ,s :start ,(or init-pos position))
                                `(parse-integer ,s :start ,(or init-pos position)
                                                   :junk-allowed t))
                         ,@(when (null (cdr vars)) `((declare (ignore ,position))))
                         ,@(expand (cdr vars))))))))
      `(let ((,s ,string))
         (declare (string ,s))
         ,@(expand vars 0)))))

(defun parse-double-float (string &key (start 0) end (declare-fixnum t))
  (declare #.OPT
           ((integer 0 #.most-positive-fixnum) start)
           (simple-base-string string))
  (let* ((end (or end (length string)))
         (minus nil)
         (point-pos -1)
         (start (loop for idx from start below end
                      do (let ((code (char-code (aref string idx))))
                           (cond ((= code #.(char-code #\-))
                                  (setq minus t)
                                  (return (1+ idx)))
                                 ((<= 48 code 57)
                                  (return idx))
                                 ((= code #.(char-code #\.))
                                  (setf point-pos idx)
                                  (return idx))
                                 ((= code #.(char-code #\+))
                                  (return (1+ idx)))))
                      finally (error "No digits found."))))
    (declare ((integer 1 #.most-positive-fixnum) end))
    (if declare-fixnum
        (loop with res of-type (integer 0 #.most-positive-fixnum) = 0
              for idx from start below end
              for code = (char-code (aref string idx))
              do (cond ((<= 48 code 57)
                        (setq res (+ (- code 48) (the fixnum (* res 10)))))
                       ((= code #.(char-code #\.))
                        (setq point-pos idx))
                       (t (loop-finish)))
              finally
                 (let ((float (* res
                                 (if (= point-pos -1)
                                     1d0
                                     (aref #.(coerce #(1d0 1d-1 1d-2 1d-3 1d-4 1d-5 1d-6 1d-7 1d-8 1d-9 1d-10 1d-11 1d-12 1d-13 1d-14 1d-15 1d-16 1d-17 1d-18 1d-19 1d-20 1d-21 1d-22 1d-23 1d-24 1d-25 1d-26 1d-27 1d-28 1d-29 1d-30 1d-31 1d-32 1d-33 1d-34 1d-35 1d-36 1d-37 1d-38 1d-39 1d-40 1d-41 1d-42 1d-43 1d-44 1d-45 1d-46 1d-47 1d-48 1d-49)
            '(simple-array double-float (*)))
                                           (- idx point-pos 1))))))
                   (declare (double-float float))
                   (return (values (if minus (- float) float)
                                   idx))))
        (error "Not implemented."))))


;; a1(ax+b)+b' = a'ax + a'b+b'
;; (a1, b1)*(a2, b2) = (a1*a2, a2*b1*b2)
(deftype box () '(cons double-float double-float))

(declaim (inline op))
(defun op (x y)
  (declare (box x y))
  (cons (* (car y) (car x))
        (+ (* (car y) (cdr x))
           (cdr y))))

(defstruct (treap (:constructor make-treap (key priority value accumulator &optional left right))
                  (:copier nil)
                  (:conc-name %treap-))
  (key 0 :type fixnum)
  (value nil :type box)
  (accumulator nil :type box)
  (priority 0 :type (integer 0 #.most-positive-fixnum))
  (left nil :type (or null treap))
  (right nil :type (or null treap)))

(declaim (inline update-accumulator))
(defun update-accumulator (treap)
  (declare (treap treap))
  (setf (%treap-accumulator treap)
        (if (%treap-left treap)
            (if (%treap-right treap)
                (op (op (%treap-accumulator (%treap-left treap))
                        (%treap-value treap))
                    (%treap-accumulator (%treap-right treap)))
                (op (%treap-accumulator (%treap-left treap))
                    (%treap-value treap)))
            (if (%treap-right treap)
                (op (%treap-value treap)
                    (%treap-accumulator (%treap-right treap)))
                (%treap-value treap)))))

(declaim (inline force-self))
(defun force-self (treap)
  (declare ((or null treap) treap))
  (update-accumulator treap))

(declaim (ftype (function * (values (or null treap) (or null treap) &optional)) treap-split))
(defun treap-split (key treap &key (test #'<))
  "Destructively splits the TREAP with reference to KEY and returns two treaps,
the smaller sub-treap (< KEY) and the larger one (>= KEY)."
  (declare #.OPT
           (function test)
           ((or null treap) treap))
  (cond ((null treap)
         (values nil nil))
        ((funcall test (%treap-key treap) key)
         (multiple-value-bind (left right)
             (treap-split key (%treap-right treap) :test test)
           (setf (%treap-right treap) left)
           (force-self treap)
           (values treap right)))
        (t
         (multiple-value-bind (left right)
             (treap-split key (%treap-left treap) :test test)
           (setf (%treap-left treap) right)
           (force-self treap)
           (values left treap)))))

(defun treap-insert (key a b treap &key (test #'<))
  "Destructively inserts KEY into TREAP and returns the result treap. You cannot
rely on the side effect. Use the returned value.

The behavior is undefined when duplicated keys are inserted."
  (declare #.OPT
           ((or null treap) treap)
           (function test))
  (labels ((recurse (node treap)
             (declare (treap node))
             (cond ((null treap) node)
                   ((> (%treap-priority node) (%treap-priority treap))
                    (setf (values (%treap-left node) (%treap-right node))
                          (treap-split (%treap-key node) treap :test test))
                    (force-self node)
                    node)
                   (t
                    (if (funcall test (%treap-key node) (%treap-key treap))
                        (setf (%treap-left treap)
                              (recurse node (%treap-left treap)))
                        (setf (%treap-right treap)
                              (recurse node (%treap-right treap))))
                    (force-self treap)
                    treap))))
    (recurse (make-treap key
                         (random most-positive-fixnum)
                         (cons a b)
                         (cons a b))
             treap)))

(defun treap-merge (left right)
  "Destructively merges two treaps. Assumes that all keys of LEFT are smaller (or larger,
depending on the order) than those of RIGHT."
  (declare #.OPT
           ((or null treap) left right))
  (cond ((null left) right)
        ((null right) left)
        ((> (%treap-priority left) (%treap-priority right))
         (setf (%treap-right left)
               (treap-merge (%treap-right left) right))
         (force-self left)
         left)
        (t
         (setf (%treap-left right)
               (treap-merge left (%treap-left right)))
         (force-self right)
         right)))

(defun treap-delete (key treap &key (test #'<))
  "Destructively deletes the KEY in TREAP and returns the result treap. Note
that this function deletes at most one node even if duplicated keys exist. You
cannot rely on the side effect. Use the returned value."
  (declare #.OPT
           ((or null treap) treap)
           (function test))
  (cond ((null treap) nil)
        ((funcall test key (%treap-key treap))
         (setf (%treap-left treap) (treap-delete key (%treap-left treap) :test test))
         (force-self treap)
         treap)
        ((funcall test (%treap-key treap) key)
         (setf (%treap-right treap) (treap-delete key (%treap-right treap) :test test))
         (force-self treap)
         treap)
        (t (treap-merge (%treap-left treap) (%treap-right treap)))))

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

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

(defconstant +mod+ 1000000007)

;; Hauptteil

(defun main ()
  (declare #.OPT)
  (let ((*read-default-float-format* 'double-float))
    (let* ((n (read))
           (m (read))
           (min 1d0)
           (max 1d0)
           (treap nil))
      (declare (uint62 n)
               (uint31 m)
               (double-float min max))
      (dotimes (i m)
        (split-objs-bind (p (a #'parse-double-float) (b #'parse-double-float))
            (buffered-read-line 35)
          (setf treap (treap-delete p treap))
          (setf treap (treap-insert p a b treap))
          (destructuring-bind (a . b) (%treap-accumulator treap)
            (declare (double-float a b))
            (let ((d (+ a b)))
              (setf min (min min d))
              (setf max (max max d))))))
      (println min)
      (println max))))

#-swank(main)

提出情報

ジャッジ結果