結果
| 問題 | No.1439 Let's Compare!!!! |
| ユーザー |
 sansaqua
|
| 提出日時 | 2021-03-26 21:45:34 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 276 ms / 2,000 ms |
| コード長 | 13,019 bytes |
| コンパイル時間 | 1,188 ms |
| コンパイル使用メモリ | 60,948 KB |
| 実行使用メモリ | 45,952 KB |
| 最終ジャッジ日時 | 2024-05-06 22:18:10 |
| 合計ジャッジ時間 | 4,551 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 12 ms
24,192 KB |
| testcase_01 | AC | 13 ms
24,192 KB |
| testcase_02 | AC | 12 ms
24,192 KB |
| testcase_03 | AC | 12 ms
24,064 KB |
| testcase_04 | AC | 14 ms
24,064 KB |
| testcase_05 | AC | 15 ms
24,064 KB |
| testcase_06 | AC | 13 ms
24,192 KB |
| testcase_07 | AC | 16 ms
24,832 KB |
| testcase_08 | AC | 17 ms
24,832 KB |
| testcase_09 | AC | 13 ms
24,192 KB |
| testcase_10 | AC | 274 ms
45,568 KB |
| testcase_11 | AC | 251 ms
36,992 KB |
| testcase_12 | AC | 246 ms
36,992 KB |
| testcase_13 | AC | 276 ms
45,824 KB |
| testcase_14 | AC | 274 ms
45,952 KB |
| testcase_15 | AC | 195 ms
37,248 KB |
| testcase_16 | AC | 135 ms
37,504 KB |
| testcase_17 | AC | 110 ms
37,376 KB |
| testcase_18 | AC | 72 ms
33,664 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 06 MAY 2024 10:18:05 PM): ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.144
ソースコード
(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))))