結果
| 問題 | No.1439 Let's Compare!!!! |
| ユーザー |
 sansaqua
|
| 提出日時 | 2021-03-26 21:45:34 |
| 言語 | Common Lisp (sbcl 2.3.8) |
| 結果 |
AC
|
| 実行時間 | 267 ms / 2,000 ms |
| コード長 | 13,019 bytes |
| コンパイル時間 | 1,293 ms |
| コンパイル使用メモリ | 61,048 KB |
| 実行使用メモリ | 54,820 KB |
| 最終ジャッジ日時 | 2024-11-29 08:39:57 |
| 合計ジャッジ時間 | 4,352 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 11 ms
28,324 KB |
| testcase_01 | AC | 11 ms
28,328 KB |
| testcase_02 | AC | 13 ms
30,280 KB |
| testcase_03 | AC | 12 ms
30,288 KB |
| testcase_04 | AC | 11 ms
28,072 KB |
| testcase_05 | AC | 12 ms
32,292 KB |
| testcase_06 | AC | 12 ms
28,204 KB |
| testcase_07 | AC | 16 ms
30,832 KB |
| testcase_08 | AC | 18 ms
32,572 KB |
| testcase_09 | AC | 13 ms
28,588 KB |
| testcase_10 | AC | 241 ms
51,160 KB |
| testcase_11 | AC | 233 ms
44,992 KB |
| testcase_12 | AC | 222 ms
44,996 KB |
| testcase_13 | AC | 256 ms
53,192 KB |
| testcase_14 | AC | 267 ms
54,820 KB |
| testcase_15 | AC | 194 ms
44,864 KB |
| testcase_16 | AC | 131 ms
43,088 KB |
| testcase_17 | AC | 111 ms
42,832 KB |
| testcase_18 | AC | 72 ms
38,860 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 29 NOV 2024 08:39:51 AM): ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.119
ソースコード
(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))))