#379455 (Common Lisp) No.885 アマリクエリ

提出ソース

結果

問題	No.885 アマリクエリ
ユーザー	sansaqua
提出日時	2019-09-14 10:37:11
言語	Common Lisp (sbcl 2.3.8)
結果	AC
実行時間	401 ms / 2,000 ms
コード長	12,784 bytes
コンパイル時間	1,192 ms
コンパイル使用メモリ	53,408 KB
実行使用メモリ	52,228 KB
最終ジャッジ日時	2023-09-19 05:10:54
合計ジャッジ時間	4,271 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	47 ms 27,572 KB
testcase_01	AC	373 ms 48,176 KB
testcase_02	AC	131 ms 33,836 KB
testcase_03	AC	61 ms 27,688 KB
testcase_04	AC	63 ms 29,248 KB
testcase_05	AC	48 ms 29,268 KB
testcase_06	AC	33 ms 25,660 KB
testcase_07	AC	44 ms 31,832 KB
testcase_08	AC	43 ms 27,560 KB
testcase_09	AC	401 ms 52,228 KB
testcase_10	AC	11 ms 25,220 KB
testcase_11	AC	9 ms 25,172 KB
testcase_12	AC	10 ms 25,116 KB
testcase_13	AC	12 ms 25,360 KB
testcase_14	AC	13 ms 25,340 KB
testcase_15	AC	14 ms 29,092 KB
testcase_16	AC	10 ms 25,276 KB
testcase_17	AC	11 ms 25,280 KB
testcase_18	AC	11 ms 25,204 KB
testcase_19	AC	11 ms 27,196 KB
testcase_20	AC	11 ms 27,268 KB
testcase_21	AC	10 ms 25,120 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

; compiling file "/home/judge/data/code/Main.lisp" (written 19 SEP 2023 05:10:49 AM):
; processing (SB-INT:DEFCONSTANT-EQX OPT ...)
; processing (SET-DISPATCH-MACRO-CHARACTER #\# ...)
; processing (DISABLE-DEBUGGER)
; processing (DEFSTRUCT (TREAP # ...) ...)
; processing (DEFUN TREAP-FIND ...)
; processing (DECLAIM (FTYPE # ...))
; processing (DEFUN TREAP-SPLIT ...)
; processing (DECLAIM (INLINE TREAP-INSERT))
; processing (DEFUN TREAP-INSERT ...)
; processing (DECLAIM (INLINE TREAP-ENSURE-KEY))
; processing (DEFUN TREAP-ENSURE-KEY ...)
; processing (DEFUN TREAP-MERGE ...)
; processing (DEFUN TREAP-DELETE ...)
; processing (DECLAIM (INLINE TREAP-MAP))
; processing (DEFUN TREAP-MAP ...)
; processing (DEFMETHOD PRINT-OBJECT ...)
; processing (DEFMACRO DO-TREAP ...)
; processing (DEFMACRO WITH-BUFFERED-STDOUT ...)
; processing (DECLAIM (FTYPE # ...))
; processing (DEFUN READ-FIXNUM ...)
; processing (DEFMACRO DBG ...)
; processing (DEFMACRO DEFINE-INT-TYPES ...)
; processing (DEFINE-INT-TYPES 2 ...)
; processing (DECLAIM (INLINE PRINTLN))
; processing (DEFUN PRINTLN ...)
; processing (DEFCONSTANT +MOD+ ...)
; processing (DEFUN MAIN ...)
; processing (MAIN)

; wrote /home/judge/data/code/Main.fasl
; compilation finished in 0:00:00.187

ソースコード

raw source code

;; -*- 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
           #\# #\> (lambda (s c p) (declare (ignore c p)) (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
;;;
;;; Treap with explicit key
;;; Virtually it works like std::map, std::multiset, or java.util.TreeMap.
;;;


;; Tips to use this structure as multiset: Just define OP as (defun op (x y) (+
;; x y)) and insert each element by (treap-ensure-key <treap> <key> 1 :if-exists
;; #'1+) instead of TREAP-INSERT.

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

(defun treap-find (treap key &key (order #'<))
  "Finds the key that satisfies (and (not (funcall order key (%treap-key
sub-treap))) (not (funcall order (%treap-key sub-treap) key))) and returns KEY
and the assigned value. Returns NIL if KEY is not contained."
  (declare (function order)
           ((or null treap) treap))
  (cond ((null treap) (values nil nil))
        ((funcall order key (%treap-key treap))
         (treap-find (%treap-left treap) key :order order))
        ((funcall order (%treap-key treap) key)
         (treap-find (%treap-right treap) key :order order))
        (t (values key (%treap-value treap)))))

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

(declaim (inline treap-insert))
(defun treap-insert (treap key value &key (order #'<))
  "Destructively inserts KEY into TREAP and returns the resultant treap. You
cannot rely on the side effect. Use the returned value.

The behavior is undefined when duplicate keys are inserted."
  (declare ((or null treap) treap)
           (function order))
  (labels ((recur (node treap)
             (declare (treap node))
             (unless treap (return-from recur node))
             (if (> (%treap-priority node) (%treap-priority treap))
                 (progn
                   (setf (values (%treap-left node) (%treap-right node))
                         (treap-split treap (%treap-key node) :order order))
                   node)
                 (progn
                   (if (funcall order (%treap-key node) (%treap-key treap))
                       (setf (%treap-left treap)
                             (recur node (%treap-left treap)))
                       (setf (%treap-right treap)
                             (recur node (%treap-right treap))))
                   treap))))
    (recur (%make-treap key (random most-positive-fixnum) value) treap)))

(declaim (inline treap-ensure-key))
(defun treap-ensure-key (treap key value &key (order #'<) if-exists)
  "IF-EXISTS := nil | function

Ensures that TREAP contains KEY and assigns VALUE to it if IF-EXISTS is
false. If IF-EXISTS is function and TREAP already contains KEY, TREAP-ENSURE-KEY
updates the value by the function instead of overwriting it with VALUE."
  (declare (function order)
           ((or null treap) treap))
  (labels ((find-and-update (treap)
             ;; Updates the value slot and returns T if KEY exists
             (unless treap (return-from find-and-update nil))
             (cond ((funcall order key (%treap-key treap))
                    (when (find-and-update (%treap-left treap))
                      t))
                   ((funcall order (%treap-key treap) key)
                    (when (find-and-update (%treap-right treap))
                      t))
                   (t (setf (%treap-value treap)
                            (if if-exists
                                (funcall if-exists (%treap-value treap))
                                value))
                      t))))
    (if (find-and-update treap)
        treap
        (treap-insert treap key value :order order))))

(defun treap-merge (left right)
  "Destructively concatenates two treaps. Assumes that all keys of LEFT are
smaller (or larger, depending on the order) than those of RIGHT."
  (declare (optimize (speed 3))
           ((or null treap) left right))
  (cond ((null left) right)
        ((null right) left)
        (t (if (> (%treap-priority left) (%treap-priority right))
               (progn
                 (setf (%treap-right left)
                       (treap-merge (%treap-right left) right))
                 left)
               (progn
                 (setf (%treap-left right)
                       (treap-merge left (%treap-left right)))
                 right)))))

(defun treap-delete (treap key &key (order #'<))
  "Destructively deletes the KEY in TREAP and returns the resultant
treap. Returns the unmodified TREAP If KEY doesn't exist. You cannot rely on the
side effect. Use the returned value.

 (Note that this function deletes at most one node even if duplicated keys
exist.)"
  (declare ((or null treap) treap)
           (function order))
  (when treap
    (cond ((funcall order key (%treap-key treap))
           (setf (%treap-left treap)
                 (treap-delete (%treap-left treap) key :order order))
           treap)
          ((funcall order (%treap-key treap) key)
           (setf (%treap-right treap)
                 (treap-delete (%treap-right treap) key :order order))
           treap)
          (t
           (treap-merge (%treap-left treap) (%treap-right treap))))))

(declaim (inline treap-map))
(defun treap-map (function treap)
  "Successively applies FUNCTION to TREAP[0], ..., TREAP[SIZE-1]. FUNCTION must
take two arguments: KEY and VALUE."
  (labels ((recur (treap)
             (when treap
               (recur (%treap-left treap))
               (funcall function (%treap-key treap) (%treap-value treap))
               (recur (%treap-right treap)))))
    (recur treap)))

(defmethod print-object ((object treap) stream)
  (print-unreadable-object (object stream :type t)
    (let ((init t))
      (treap-map (lambda (key value)
                   (if init
                       (setf init nil)
                       (write-char #\  stream))
                   (format stream "<~A . ~A>" key value))
                 object))))

(defmacro do-treap ((key-var value-var treap &optional result) &body body)
  "Successively binds the key and value of INODE[0], ..., INODE[SIZE-1] to
KEY-VAR and VALUE-VAR and executes BODY."
  `(block nil
     (treap-map (lambda (,key-var ,value-var) ,@body) ,treap)
     ,result))

;; Should we do this with UNWIND-PROTECT?
(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)))))

(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 main ()
  (declare #.OPT)
  (let* ((n (read))
         treap
         (sum 0))
    (declare (uint62 n sum))
    (dotimes (i n)
      (let ((a (read-fixnum)))
        (incf sum a)
        (setq treap (treap-ensure-key treap a 1 :if-exists #'1+))))
    (let ((q (read)))
      (declare (uint32 q))
      (with-buffered-stdout
        (dotimes (i q)
          (let ((x (read-fixnum)))
            (multiple-value-bind (left right) (treap-split treap x)
              (setq treap left)
              (do-treap (key count right)
                (declare (uint31 key count))
                (let ((new-key (mod key x)))
                  (declare (uint31 new-key))
                  (setq treap (treap-ensure-key treap new-key count :if-exists (lambda (i) (+ i count))))
                  (decf sum (* count (- key new-key)))))
              (println sum))))))))

#-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:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

#+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 "")))

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード