結果

問題 No.1439 Let's Compare!!!!
ユーザー sansaquasansaqua
提出日時 2021-03-26 21:45:34
言語 Common Lisp
(sbcl 2.3.8)
結果
AC  
実行時間 202 ms / 2,000 ms
コード長 13,019 bytes
コンパイル時間 1,529 ms
コンパイル使用メモリ 50,052 KB
実行使用メモリ 51,708 KB
最終ジャッジ日時 2023-08-19 15:14:04
合計ジャッジ時間 4,373 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
24,820 KB
testcase_01 AC 7 ms
24,892 KB
testcase_02 AC 8 ms
24,836 KB
testcase_03 AC 8 ms
28,684 KB
testcase_04 AC 8 ms
24,692 KB
testcase_05 AC 8 ms
28,564 KB
testcase_06 AC 7 ms
24,768 KB
testcase_07 AC 12 ms
27,348 KB
testcase_08 AC 12 ms
27,352 KB
testcase_09 AC 9 ms
25,004 KB
testcase_10 AC 202 ms
51,708 KB
testcase_11 AC 189 ms
39,608 KB
testcase_12 AC 193 ms
43,152 KB
testcase_13 AC 202 ms
47,880 KB
testcase_14 AC 198 ms
47,784 KB
testcase_15 AC 167 ms
39,648 KB
testcase_16 AC 120 ms
41,664 KB
testcase_17 AC 103 ms
39,560 KB
testcase_18 AC 74 ms
35,532 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 19 AUG 2023 03:13:59 PM):
; processing (IN-PACKAGE :CL-USER)
; processing (DEFPARAMETER *OPT* ...)
; processing (SET-DISPATCH-MACRO-CHARACTER #\# ...)
; processing (DOLIST (F #) ...)
; processing (SETQ *RANDOM-STATE* ...)
; processing (DEFINE-INT-TYPES 2 ...)
; processing (DEFCONSTANT +MOD+ ...)
; processing (DEFMACRO DBG ...)
; processing (DECLAIM (INLINE PRINTLN))
; processing (DEFUN PRINTLN ...)
; processing (DEFPACKAGE :CP/TREAP ...)
; processing (IN-PACKAGE :CP/TREAP)
; processing (DEFSTRUCT (TREAP # ...) ...)
; processing (DECLAIM (INLINE TREAP-KEY))
; processing (DEFUN TREAP-KEY ...)
; processing (DECLAIM (INLINE TREAP-FIND))
; processing (DEFUN TREAP-FIND ...)
; processing (DECLAIM (INLINE TREAP-SPLIT))
; processing (DEFUN TREAP-SPLIT ...)
; processing (DECLAIM (INLINE TREAP-INSERT))
; processing (DEFUN TREAP-INSERT ...)
; processing (DECLAIM (INLINE TREAP-MAP))
; processing (DEFUN TREAP-MAP ...)
; processing (DEFMETHOD PRINT-OBJECT ...)
; processing (DECLAIM (FTYPE # ...))
; processing (DEFUN TREAP-MERGE ...)
; processing (DECLAIM (INLINE TREAP-DELETE))
; processing (DEFUN TREAP-DELETE ...)
; processing (DEFMACRO TREAP-PUSH ...)
; processing (DEFMACRO TREAP-POP ...)
; processing (DEFUN TREAP-FIRST ...)
; processing (DEFUN TREAP-LAST ...)
; processing (DECLAIM (FTYPE # ...))
; processing (DEFUN TREAP-COUNT ...)
; processing (DECLAIM (INLINE TREAP-BISECT-LEFT))
; processing (DEFUN TREAP-BISECT-LEFT ...)
; processing (DEFPACKAGE :CP/READ-FIXNUM ...)
; processing (IN-PACKAGE :CP/READ-FIXNUM)
; processing (DECLAIM (FTYPE # ...))
; processing (DEFUN READ-FIXNUM ...)
; processing (USE-PACKAGE :CP/READ-FIXNUM ...)
; processing (USE-PACKAGE :CP/TREAP ...)
; processing (IN-PACKAGE :CL-USER)
; processing (DEFUN MAIN ...)
; processing (MAIN)

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

ソースコード

diff #

(in-package :cl-user)
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter *opt*
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload '(:cl-debug-print :fiveam :cp/util) :silent t)
  #+swank (use-package :cp/util :cl-user)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t))))
  #+sbcl (dolist (f '(:popcnt :sse4)) (pushnew f sb-c:*backend-subfeatures*))
  #+sbcl (setq *random-state* (seed-random-state (nth-value 1 (get-time-of-day)))))
#-swank (eval-when (:compile-toplevel)
          (setq *break-on-signals* '(and warning (not style-warning))))
#+swank (set-dispatch-macro-character #\# #\> #'cl-debug-print:debug-print-reader)

(macrolet ((def (b)
             `(progn (deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))
                     (deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))))
           (define-int-types (&rest bits) `(progn ,@(mapcar (lambda (b) `(def ,b)) bits))))
  (define-int-types 2 4 7 8 15 16 31 32 62 63 64))

(defconstant +mod+ 1000000007)

(defmacro dbg (&rest forms)
  (declare (ignorable forms))
  #+swank (if (= (length forms) 1)
              `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
              `(format *error-output* "~A => ~A~%" ',forms `(,,@forms))))

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format*
          (if (typep obj 'double-float) 'double-float *read-default-float-format*)))
    (prog1 (princ obj stream) (terpri stream))))

;; BEGIN_INSERTED_CONTENTS
(defpackage :cp/treap
  (:use :cl)
  (:export #:treap #:treap-count #:treap-find #:treap-bisect-left
           #:treap-split #:treap-insert #:treap-push #:treap-pop #:treap-delete #:treap-merge
           #:treap-map #:invalid-treap-index-error #:treap-first #:treap-last))
(in-package :cp/treap)

;; Not included in test script. Better to use ref-able-treap instead.

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

(declaim (inline treap-key))
(defun treap-key (treap)
  (and treap (%treap-key treap)))

(declaim (inline treap-find))
(defun treap-find (key treap &key (order #'<))
  "Searches the sub-treap of TREAP whose key satisfies (and (not (funcall order
key (%treap-key sub-treap))) (not (funcall order (%treap-key sub-treap) key))) and
returns KEY. Returns NIL if KEY is not contained."
  (declare ((or null treap) treap))
  (labels ((recur (treap)
             (cond ((null treap) nil)
                   ((funcall order key (%treap-key treap))
                    (recur (%treap-left treap)))
                   ((funcall order (%treap-key treap) key)
                    (recur (%treap-right treap)))
                   (t key))))
    (recur treap)))

(declaim (inline treap-split))
(defun treap-split (key treap &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 ((or null treap) treap))
  (labels ((recur (treap)
             (cond ((null treap)
                    (values nil nil))
                   ((funcall order (%treap-key treap) key)
                    (multiple-value-bind (left right)
                        (recur (%treap-right treap))
                      (setf (%treap-right treap) left)
                      (values treap right)))
                   (t
                    (multiple-value-bind (left right)
                        (recur (%treap-left treap))
                      (setf (%treap-left treap) right)
                      (values left treap))))))
    (recur treap)))

(declaim (inline treap-insert))
(defun treap-insert (key treap &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))
  (labels ((recur (new-node treap)
             (declare (treap new-node))
             (cond ((null treap) new-node)
                   ((> (%treap-priority new-node) (%treap-priority treap))
                    (setf (values (%treap-left new-node) (%treap-right new-node))
                          (treap-split (%treap-key new-node) treap :order order))
                    new-node)
                   (t
                    (if (funcall order (%treap-key new-node) (%treap-key treap))
                        (setf (%treap-left treap)
                              (recur new-node (%treap-left treap)))
                        (setf (%treap-right treap)
                              (recur new-node (%treap-right treap))))
                    treap))))
    (recur (%make-treap key (random most-positive-fixnum)) treap)))

(declaim (inline treap-map))
(defun treap-map (function treap)
  "Successively applies FUNCTION to each key of TREAP in the given
order. FUNCTION must take one argument."
  (declare (function function))
  (labels ((recur (treap)
             (when treap
               (recur (%treap-left treap))
               (funcall function (%treap-key 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)
                   (if init
                       (setf init nil)
                       (write-char #\  stream))
                   (write key :stream stream))
                 object))))

(declaim (ftype (function * (values (or null treap) &optional)) treap-merge))
(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)
        ((> (%treap-priority left) (%treap-priority right))
         (setf (%treap-right left)
               (treap-merge (%treap-right left) right))
         left)
        (t
         (setf (%treap-left right)
               (treap-merge left (%treap-left right)))
         right)))

(declaim (inline treap-delete))
(defun treap-delete (key treap &key (order #'<))
  "Destructively deletes the KEY in TREAP and returns the resultant treap. You
cannot rely on the side effect. Use the returned value."
  (declare ((or null treap) treap))
  (labels ((recur (treap)
             (cond ((null treap) nil)
                   ((funcall order key (%treap-key treap))
                    (setf (%treap-left treap) (recur (%treap-left treap)))
                    treap)
                   ((funcall order (%treap-key treap) key)
                    (setf (%treap-right treap) (recur (%treap-right treap)))
                    treap)
                   (t
                    (treap-merge (%treap-left treap) (%treap-right treap))))))
    (recur treap)))

(defmacro treap-push (key treap &optional (order '#'<))
  "Pushes a KEY to TREAP."
  `(setf ,treap (treap-insert ,key ,treap :order ,order)))

(defmacro treap-pop (key treap &optional (order '#'<))
  "Deletes a KEY from TREAP."
  `(setf ,treap (treap-delete ,key ,treap :order ,order)))

(defun treap-first (treap)
  (declare (optimize (speed 3))
           (treap treap))
  (if (%treap-left treap)
      (treap-first (%treap-left treap))
      (%treap-key treap)))

(defun treap-last (treap)
  (declare (optimize (speed 3))
           (treap treap))
  (if (%treap-right treap)
      (treap-last (%treap-right treap))
      (%treap-key treap)))

(declaim (ftype (function * (values (integer 0 #.most-positive-fixnum) &optional))
                treap-count))
(defun treap-count (treap)
  "Counts the number of elements in TREAP in O(n) time."
  (declare (optimize (speed 3))
           ((or null treap) treap))
  (labels ((recur (treap)
             (declare (optimize (safety 0)))
             (if (null treap)
                 0
                 (+ 1
                    (treap-count (%treap-left treap))
                    (treap-count (%treap-right treap))))))
    (recur treap)))

(declaim (inline treap-bisect-left))
(defun treap-bisect-left (treap key &key (order #'<))
  "Returns the smallest key equal to or larger than KEY. Returns NIL if KEY is
larger than any keys in TREAP."
  (declare ((or null treap) treap))
  (labels ((recur (treap)
             (cond ((null treap) nil)
                   ((funcall order (%treap-key treap) key)
                    (recur (%treap-right treap)))
                   (t (or (recur (%treap-left treap))
                          treap)))))
    (treap-key (recur treap))))

(defpackage :cp/read-fixnum
  (:use :cl)
  (:export #:read-fixnum))
(in-package :cp/read-fixnum)

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (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 #\-))
                                  (setq 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))))))))

;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/read-fixnum :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/treap :cl-user))
(in-package :cl-user)

;;;
;;; Body
;;;

(defun main ()
  (let* ((n (read))
         (ss (map '(simple-array uint8 (*)) #'digit-char-p (read-line)))
         (tt (map '(simple-array uint8 (*)) #'digit-char-p (read-line)))
         treap)
    (dotimes (i n)
      (let ((d1 (aref ss i))
            (d2 (aref tt i)))
        (unless (= d1 d2)
          (treap-push i treap))))
    (let ((q (read)))
      (write-string
       (with-output-to-string (*standard-output* nil :element-type 'base-char)
         (dotimes (_ q)
           (let* ((c (read-char))
                  (x (- (read-fixnum) 1))
                  (y (read-fixnum))
                  (s (ecase c (#\T tt) (#\S ss))))
             (unless (= (aref ss x) (aref tt x))
               (treap-pop x treap))
             (setf (aref s x) y)
             (unless (= (aref ss x) (aref tt x))
               (treap-push x treap)))
           (write-line
            (if (null treap)
                "="
                (let ((pos0 (treap-first treap)))
                  (cond ((> (aref ss pos0) (aref tt pos0))
                         ">")
                        ((< (aref ss pos0) (aref tt pos0))
                         "<")
                        (t (error "Huh?"))))))))))))

#-swank (main)

;;;
;;; Test
;;;

#+swank
(progn
  (defparameter *lisp-file-pathname* (uiop:current-lisp-file-pathname))
  (setq *default-pathname-defaults* (uiop:pathname-directory-pathname *lisp-file-pathname*))
  (uiop:chdir *default-pathname-defaults*)
  (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *lisp-file-pathname*))
  (defparameter *problem-url* "https://yukicoder.me/problems/no/1439"))

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

#+(and sbcl (not swank))
(eval-when (:compile-toplevel)
  (when sb-c::*undefined-warnings*
    (error "undefined warnings: ~{~A~^ ~}" sb-c::*undefined-warnings*)))

;; To run: (5am:run! :sample)
#+swank
(5am:test :sample
  (5am:is
   (equal ">
<
<
<
"
          (run "5
45218
08809
4
T 1 3
S 1 2
T 1 2
T 4 6
" nil)))
  (5am:is
   (equal ">
>
>
>
>
>
>
<
>
>
>
>
>
>
>
>
>
<
<
<
"
          (run "20
40565756273027673892
10905458842553731367
20
S 1 9
T 5 5
S 19 8
T 12 3
S 20 9
S 9 9
S 1 3
S 1 0
S 1 5
T 19 7
S 2 9
T 18 7
T 20 0
S 5 7
T 1 5
T 11 3
T 5 3
S 1 1
S 1 1
S 10 6
" nil))))
0