結果
問題 | No.885 アマリクエリ |
ユーザー | sansaqua |
提出日時 | 2019-09-13 23:06:40 |
言語 | Common Lisp (sbcl 2.5.0) |
結果 |
AC
|
実行時間 | 308 ms / 2,000 ms |
コード長 | 9,877 bytes |
コンパイル時間 | 305 ms |
コンパイル使用メモリ | 65,536 KB |
実行使用メモリ | 34,048 KB |
最終ジャッジ日時 | 2024-07-04 10:21:47 |
合計ジャッジ時間 | 2,890 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 308 ms
30,976 KB |
testcase_01 | AC | 127 ms
32,512 KB |
testcase_02 | AC | 106 ms
34,048 KB |
testcase_03 | AC | 79 ms
30,848 KB |
testcase_04 | AC | 78 ms
30,976 KB |
testcase_05 | AC | 56 ms
30,720 KB |
testcase_06 | AC | 38 ms
30,848 KB |
testcase_07 | AC | 30 ms
23,296 KB |
testcase_08 | AC | 50 ms
30,464 KB |
testcase_09 | AC | 146 ms
32,512 KB |
testcase_10 | AC | 9 ms
22,784 KB |
testcase_11 | AC | 9 ms
22,784 KB |
testcase_12 | AC | 8 ms
22,784 KB |
testcase_13 | AC | 10 ms
22,912 KB |
testcase_14 | AC | 9 ms
22,912 KB |
testcase_15 | AC | 9 ms
23,040 KB |
testcase_16 | AC | 9 ms
22,912 KB |
testcase_17 | AC | 9 ms
22,912 KB |
testcase_18 | AC | 9 ms
22,912 KB |
testcase_19 | AC | 8 ms
22,784 KB |
testcase_20 | AC | 7 ms
22,912 KB |
testcase_21 | AC | 7 ms
22,784 KB |
コンパイルメッセージ
; compiling file "/home/judge/data/code/Main.lisp" (written 04 JUL 2024 10:21:44 AM): ; file: /home/judge/data/code/Main.lisp ; in: SB-C:DEFTRANSFORM ARRAY-ELEMENT-TYPE ; (SB-C:DEFTRANSFORM ARRAY-ELEMENT-TYPE ; ((ARRAY)) ; (LET ((TYPE (SB-C::LVAR-TYPE ARRAY))) ; (FLET ((ELEMENT-TYPE # ; #)) ; (COND (#) (# #) (# #) (T #))))) ; ; caught STYLE-WARNING: ; Overwriting #<SB-C::TRANSFORM FUNCTION {100033B4E3}> ; ; compilation unit finished ; caught 1 STYLE-WARNING condition ; wrote /home/judge/data/code/Main.fasl ; compilation finished in 0:00:00.149
ソースコード
;; -*- 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;; 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 onlyBASE-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)))));;;;;; ARRAY-ELEMENT-TYPE is not constant-folded on SBCL version earlier than;;; 1.5.0. See;;; https://github.com/sbcl/sbcl/commit/9f0d12e7ab961828931d01c0b2a76a5885ad35d2;;;(eval-when (:compile-toplevel :load-toplevel :execute)(sb-c:deftransform array-element-type ((array))(let ((type (sb-c::lvar-type array)))(flet ((element-type (type)(and (sb-c::array-type-p type)(sb-int:neq (sb-kernel::array-type-specialized-element-type type) sb-kernel:*wild-type*)(sb-kernel:type-specifier (sb-kernel::array-type-specialized-element-type type)))))(cond ((let ((type (element-type type)))(and type`',type)))((sb-kernel:union-type-p type)(let (result)(loop for type in (sb-kernel:union-type-types type)for et = (element-type type)unless (and et(if result(equal result et)(setf result et)))do (sb-c::give-up-ir1-transform))`',result))((sb-kernel:intersection-type-p type)(loop for type in (sb-kernel:intersection-type-types type)for et = (element-type type)when etreturn `',etfinally (sb-c::give-up-ir1-transform)))(t(sb-c::give-up-ir1-transform)))))));; On SBCL version earlier than 1.5.6 this type deriver is necessary for;; MAKE-ARRAY to propagate the element type of a multi-dimensional array. It is;; a dead copy of the commit;; https://github.com/sbcl/sbcl/commit/c84daa0791f4d4ed03469fc23a1d1bc2aadacda2(eval-when (:compile-toplevel :load-toplevel :execute)(sb-c:defoptimizer (sb-c::make-array-header* sb-c::derive-type) ((&rest inits))(let* ((data-position #.(sb-vm::slot-offset(find 'sb-vm::data (sb-vm:primitive-object-slots(find 'array sb-vm:*primitive-objects*:key 'sb-vm:primitive-object-name)):key 'sb-vm::slot-name)))(data (nth data-position inits))(type (sb-c::lvar-type data)))(when (sb-kernel:array-type-p type)(sb-kernel:make-array-type '*:element-type (sb-kernel:array-type-element-type type):specialized-element-type (sb-kernel:array-type-specialized-element-type type))))))(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))))))));;;;;; Disjoint sparse table on arbitrary semigroup;;;;;; Reference:;;; https://discuss.codechef.com/questions/117696/tutorial-disjoint-sparse-table;;; http://noshi91.hatenablog.com/entry/2018/05/08/183946 (Japanese);;; http://drken1215.hatenablog.com/entry/2018/09/08/162600 (Japanese);; NOTE: This constructor is slow on SBCL version earlier than 1.5.6 as the type;; propagation of MAKE-ARRAY doesn't work. The following files are required to;; enable the optimization.;; version < 1.5.0: array-element-type.lisp, make-array-header.lisp;; version < 1.5.6: make-array-header.lisp(declaim (inline make-disjoint-sparse-table))(defun make-disjoint-sparse-table (vector binop)"BINOP := binary operator (comprising a semigroup)"(let* ((n (length vector))(height (integer-length (- n 1)))(table (make-array (list height n) :element-type (array-element-type vector))))(dotimes (j n)(setf (aref table 0 j) (aref vector j)))(do ((i 1 (+ i 1)))((>= i height))(let* ((width/2 (ash 1 i))(width (* width/2 2)))(do ((j 0 (+ j width)))((>= j n))(let ((mid (min (+ j width/2) n)));; fill the first half(setf (aref table i (- mid 1))(aref vector (- mid 1)))(do ((k (- mid 2) (- k 1)))((< k j))(setf (aref table i k)(funcall binop (aref vector k) (aref table i (+ k 1)))))(when (>= mid n)(return));; fill the second half(setf (aref table i mid)(aref vector mid))(let ((end (min n (+ mid width/2))))(do ((k (+ mid 1) (+ k 1)))((>= k end))(setf (aref table i k)(funcall binop (aref table i (- k 1)) (aref vector k)))))))))table))(declaim (inline dst-query))(defun dst-query (table binop left right &optional identity)"Queries the interval [LEFT, RIGHT). Returns IDENTITY for a null interval [x,x)."(declare ((integer 0 #.most-positive-fixnum) left right)((simple-array * (* *)) table))(when (>= left right)(return-from dst-query identity))(setq right (- right 1)) ;; change to closed interval(if (= left right)(aref table 0 left)(let ((h (- (integer-length (logxor left right)) 1)))(funcall binop(aref table h left)(aref table h right)))))(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))(as (make-array n :element-type 'uint32)))(dotimes (i n) (setf (aref as i) (read-fixnum)))(let* ((q (read))(xs (make-array q :element-type 'uint32))(deltas (make-array q :element-type 'uint62 :initial-element 0)))(dotimes (i q) (setf (aref xs i) (read-fixnum)))(let ((dtable (make-disjoint-sparse-table xs #'min)))(declare ((simple-array uint32 (* *)) dtable))(dotimes (i n)(let ((value (aref as i))(prev-pos 0))(declare (fixnum value prev-pos))(loop(unless (<= (dst-query dtable #'min prev-pos q #xffffffff) value)(return))(let* ((new-pos (sb-int:named-let bisect ((ng prev-pos) (ok q))(declare (int32 ng ok))(if (<= (- ok ng) 1)(- ok 1)(let* ((mid (ash (+ ng ok) -1))(min (dst-query dtable #'min prev-pos mid #xffffffff)))(if (<= min value)(bisect ng mid)(bisect mid ok))))))(new-value (mod value (aref xs new-pos))))(incf (aref deltas new-pos) (- value new-value))(setq prev-pos new-posvalue new-value))))))(let ((sum (reduce #'+ as)))(declare (fixnum sum))(with-buffered-stdout(dotimes (i q)(decf sum (aref deltas i))(println sum)))))))#-swank (main)