Submission #5623667

---

Source Code Expand

;; -*- coding: utf-8 -*-
(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 with-output-buffer (&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)))))

(setf *print-circle* t)

;; Treap with implicit key for updating and querying interval.

(declaim (inline op))
(defun op (a b)
  (+ a b))

(defconstant +op-identity+ 0)

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

(declaim (inline inode-count))
(defun inode-count (inode)
  (declare ((or null inode) inode))
  (if inode
      (%inode-count inode)
      0))

(declaim (inline inode-accumulator))
(defun inode-accumulator (inode)
  (declare ((or null inode) inode))
  (if inode
      (%inode-accumulator inode)
      +op-identity+))

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

(declaim (inline update-accumulator))
(defun update-accumulator (inode)
  (declare (inode inode))
  (setf (%inode-accumulator inode)
        (if (%inode-left inode)
            (if (%inode-right inode)
                (let ((mid (op (%inode-accumulator (%inode-left inode))
                               (%inode-value inode))))
                  (declare (dynamic-extent mid) (fixnum mid))
                  (op mid (%inode-accumulator (%inode-right inode))))
                (op (%inode-accumulator (%inode-left inode))
                    (%inode-value inode)))
            (if (%inode-right inode)
                (op (%inode-value inode)
                    (%inode-accumulator (%inode-right inode)))
                (%inode-value inode)))))

(declaim (inline force-self))
(defun force-self (inode)
  (declare (inode inode))
  (update-count inode)
  (update-accumulator inode))


(defun inode-split (inode index)
  "Destructively splits the INODE into two nodes [0, INDEX) and [INDEX, N), where N
  is the number of elements of the INODE."
  (declare #.OPT ((integer 0 #.most-positive-fixnum) index))
  (unless inode
    (return-from inode-split (values nil nil)))
  (let ((implicit-key (1+ (inode-count (%inode-left inode)))))
    (if (< index implicit-key)
        (multiple-value-bind (left right)
            (inode-split (%inode-left inode) index)
          (setf (%inode-left inode) right)
          (force-self inode)
          (values left inode))
        (multiple-value-bind (left right)
            (inode-split (%inode-right inode) (- index implicit-key))
          (setf (%inode-right inode) left)
          (force-self inode)
          (values inode right)))))

(defun inode-merge (left right)
  "Destructively merges two INODEs."
  (declare #.OPT ((or null inode) left right))
  (cond ((null left) (when right (force-self right)) right)
        ((null right) (when left (force-self left)) left)
        (t (if (> (%inode-priority left) (%inode-priority right))
               (progn
                 (setf (%inode-right left)
                       (inode-merge (%inode-right left) right))
                 (force-self left)
                 left)
               (progn
                 (setf (%inode-left right)
                       (inode-merge left (%inode-left right)))
                 (force-self right)
                 right)))))

(declaim (inline inode-insert))
(defun inode-insert (inode index obj)
  "Destructively inserts OBJ into INODE at INDEX."
  (declare ((or null inode) inode)
           ((integer 0 #.most-positive-fixnum) index))
  (assert (<= index (inode-count inode)))
  (let ((obj-inode (%make-inode obj (random most-positive-fixnum))))
    (multiple-value-bind (left right)
        (inode-split inode index)
      (inode-merge (inode-merge left obj-inode) right))))

(defun inode-map (function inode)
  "Successively applies FUNCTION to INODE[0], ..., INODE[SIZE-1]."
  (declare (function function))
  (when inode
    (inode-map function (%inode-left inode))
    (funcall function (%inode-value inode))
    (inode-map function (%inode-right inode))
    (force-self inode)))

(defmethod print-object ((object inode) stream)
  (print-unreadable-object (object stream :type t)
    (let ((size (inode-count object))
          (index 0))
      (declare ((integer 0 #.most-positive-fixnum) index))
      (inode-map (lambda (x)
                   (princ x stream)
                   (incf index)
                   (when (< index size)
                     (write-char #\  stream)))
                 object))))

(declaim (inline inode-ref))
(defun inode-ref (inode index)
  (declare ((integer 0 #.most-positive-fixnum) index))
  (assert (< index (inode-count inode)))
  (labels ((%ref (inode index)
             (declare ((integer 0 #.most-positive-fixnum) index))
             (prog1
                 (let ((left-count (inode-count (%inode-left inode))))
                   (cond ((< index left-count)
                          (%ref (%inode-left inode) index))
                         ((> index left-count)
                          (%ref (%inode-right inode) (- index left-count 1)))
                         (t (%inode-value inode))))
               (force-self inode))))
    (%ref inode index)))

(declaim (inline inode-bisect-left))
(defun inode-bisect-left (threshold treap &key (order #'<))
  "Returns the smallest index and the corresponding key that satisfies
KEY[index] >= THRESHOLD. Returns the size of TREAP and THRESHOLD if KEY[size-1]
< THRESHOLD."
  (declare (function order))
  (labels ((recur (count treap)
             (declare ((integer 0 #.most-positive-fixnum) count))
             (cond ((null treap) nil)
                   ((funcall order (%inode-value treap) threshold)
                    (recur count (%inode-right treap)))
                   (t (let ((left-count (- count (inode-count (%inode-right treap)) 1)))
                        (or (recur left-count (%inode-left treap))
                            left-count))))))
    (or (recur (inode-count treap) treap)
        (inode-count treap))))

(declaim (inline inode-query))
(defun inode-query (inode &key (start 0) end)
  "Queries the sum of the half-open interval specified by the index: [START,
END). If START (END) is not given, it is assumed to be 0 (the size of INODE)."
  (declare ((integer 0 #.most-positive-fixnum) start)
           ((or null (integer 0 #.most-positive-fixnum)) end))
  (if (zerop start)
      (if (null end)
          (inode-accumulator inode)
          (multiple-value-bind (inode-0-r inode-r-n)
              (inode-split inode end)
            (prog1 (inode-accumulator inode-0-r)
              (inode-merge inode-0-r inode-r-n))))
      (if (null end)
          (multiple-value-bind (inode-0-l inode-l-n)
              (inode-split inode start)
            (prog1 (inode-accumulator inode-l-n)
              (inode-merge inode-0-l inode-l-n)))
          (progn
            (assert (<= start end))
            (multiple-value-bind (inode-0-l inode-l-n)
                (inode-split inode start)
              (multiple-value-bind (inode-l-r inode-r-n)
                  (inode-split inode-l-n end)
                (prog1 (inode-accumulator inode-l-r)
                  (inode-merge inode-0-l (inode-merge inode-l-r inode-r-n)))))))))

(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
                                  ;; (return-from read-fixnum 0)
                                  (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 main ()
  (declare #.OPT)
  (let* ((q (read))
         (const 0)
         inode)
    (declare (uint32 q) (fixnum const))
    (with-output-buffer
      (dotimes (i q)
        (let ((id (read-fixnum)))
          (if (= id 1)
              (let ((a (read-fixnum))
                    (b (read-fixnum)))
                (setf inode (inode-insert inode (inode-bisect-left a inode) a))
                (incf const b))
              (let ((count (inode-count inode)))
                (if (oddp count)
                    (let* ((mid (floor count 2))
                           (at (inode-ref inode mid)))
                      (format t
                              "~D ~D~%"
                              at
                              (+ const
                                 (inode-query inode :start (+ mid 1))
                                 (- (inode-query inode :end mid)))))
                    (let* ((mid (floor count 2))
                           (at (inode-ref inode (- mid 1))))
                      (format t
                              "~D ~D~%"
                              at
                              (+ const
                                 (inode-query inode :start mid)
                                 (- (inode-query inode :end mid)))))))))))))

#-swank(main)

Submission Info

Judge Result