#618556 (Common Lisp) No.1338 Giant Class

提出ソース

結果

問題	No.1338 Giant Class
ユーザー	Endered
提出日時	2021-02-15 20:15:53
言語	Common Lisp (sbcl 2.3.8)
結果	AC
実行時間	355 ms / 2,000 ms
コード長	8,189 bytes
コンパイル時間	963 ms
コンパイル使用メモリ	54,800 KB
実行使用メモリ	47,912 KB
最終ジャッジ日時	2024-07-23 12:09:35
合計ジャッジ時間	7,255 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
	外部呼び出し有り

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	20 ms 29,096 KB
testcase_01	AC	21 ms 30,800 KB
testcase_02	AC	281 ms 35,396 KB
testcase_03	AC	21 ms 28,968 KB
testcase_04	AC	21 ms 29,100 KB
testcase_05	AC	22 ms 30,524 KB
testcase_06	AC	210 ms 43,580 KB
testcase_07	AC	292 ms 45,728 KB
testcase_08	AC	199 ms 43,544 KB
testcase_09	AC	183 ms 39,484 KB
testcase_10	AC	315 ms 47,912 KB
testcase_11	AC	49 ms 35,312 KB
testcase_12	AC	228 ms 41,892 KB
testcase_13	AC	216 ms 39,488 KB
testcase_14	AC	71 ms 33,344 KB
testcase_15	AC	96 ms 33,340 KB
testcase_16	AC	47 ms 31,272 KB
testcase_17	AC	213 ms 39,496 KB
testcase_18	AC	72 ms 33,600 KB
testcase_19	AC	112 ms 33,600 KB
testcase_20	AC	355 ms 43,844 KB
testcase_21	AC	354 ms 45,872 KB
testcase_22	AC	355 ms 43,844 KB

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

コンパイルメッセージ

; compiling file "/home/judge/data/code/Main.lisp" (written 23 JUL 2024 12:09:28 PM):

; file: /home/judge/data/code/Main.lisp
; in: DEFMACRO TEST
;     (DEFMACRO TEST ((FUNC &BODY ARGS) &OPTIONAL (OUT-STREAM))
;       (LET ((EVALED-ARGS (GENSYM)))
;         `(LET ((,EVALED-ARGS #))
;            (FORMAT T "~w: ~w ~%" `(,',FUNC ,@,EVALED-ARGS)
;                    (APPLY #',FUNC ,EVALED-ARGS)))))
; --> EVAL-WHEN SB-C::%DEFMACRO SB-INT:NAMED-LAMBDA SB-INT:NAMED-DS-BIND 
; --> SB-INT:BINDING* 
; ==>
;   (LET* ((#:G0 (SB-C::CHECK-DS-LIST (CDR #:EXPR) 1 2 '(# # &OPTIONAL #)))
;          (#:G1 (SB-C::CHECK-DS-LIST/&REST (POP #:G0) 1 1 '(# FUNC &BODY ARGS)))
;          (FUNC (POP #:G1))
;          (ARGS #:G1)
;          (OUT-STREAM
;           (IF #:G0
;               (POP #:G0))))
;     (DECLARE (SB-C::CONSTANT-VALUE FUNC ARGS OUT-STREAM))
;     (BLOCK TEST
;       (LET ((EVALED-ARGS #))
;         `(LET (#)
;            (FORMAT T "~w: ~w ~%" `# #)))))
; 
; caught STYLE-WARNING:
;   The variable OUT-STREAM is defined but never used.

; file: /home/judge/data/code/Main.lisp
; in: DEFMACRO TEST
;     (DEFMACRO TEST ((FUNC &BODY ARGS) &OPTIONAL (OUT-STREAM))
;       (LET ((EVALED-ARGS (GENSYM)))
;         `(LET ((,EVALED-ARGS #))
;            (FORMAT T "~w: ~w ~%" `(,',FUNC ,@,EVALED-ARGS)
;                    (APPLY #',FUNC ,EVALED-ARGS)))))
; --> EVAL-WHEN SB-C::%DEFMACRO SB-C::%DEFMACRO SB-INT:NAMED-LAMBDA FUNCTION 
; --> SB-INT:NAMED-DS-BIND SB-INT:BINDING* 
; ==>
;   (LET* ((#:G0 (SB-C::CHECK-DS-LIST (CDR #:EXPR) 1 2 '(# # &OPTIONAL #)))
;          (#:G1 (SB-C::CHECK-DS-LIST/&REST (POP #:G0) 1 1 '(# FUNC &BODY ARGS)))
;          (FUNC (POP #:G1))
;          (ARGS #:G1)
;          (OUT-STREAM
;           (IF #:G0
;               (POP #:G0))))
;     (DECLARE (SB-C::CONSTANT-VALUE FUNC ARGS OUT-STREAM))
;     (BLOCK TEST
;       (LET ((EVALED-ARGS #))
;         `(LET (#)
;            (FORMAT T "~w: ~w ~%" `# #)))))
; 
; caught STYLE-WARNING:
;   The variable OUT-STREAM is d

ソースコード

raw source code

#-swank
(unless (member :child-sbcl *features*)
  "I refered from https://competitive12.blogspot.com/2020/03/common-lisp.html thank you!"
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "256MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
(defmacro dpline (name args memo-size &body body)
  (let ((memo (gensym)))
    `(let ((,memo (make-array ,memo-size :initial-element nil)))
       (defun ,name ,args
         (or (aref ,memo ,@args)
             (setf (aref ,memo ,@args)
                   ,@body))))))

(defmacro dphash (name args &body expr)
  `(let ((table (make-hash-table :test #'equal)))
     (defun  ,name ,args 
       (or (gethash (list ,@args) table)
           (setf (gethash (list ,@args) table)
                 (progn 
                   ,@expr))))))

(defmacro test ((func &body args) &optional (out-stream))
  (let ((evaled-args (gensym)))
    `(let ((,evaled-args (list ,@args)))
       (format t "~w: ~w ~%" `(,',func ,@,evaled-args) (apply #',func ,evaled-args)))))

(defmacro dplabels (funcs &body body)
  (let ((tables (loop for func in funcs collect (gensym))))
    `(let ,(mapcar (lambda (table) `(,table (make-hash-table :test #'equal)))
            tables)
       (labels ,(mapcar (lambda (func table)
                          (let ((name (first func))
                                (args (second func))
                                (body (cddr func))
                                (ok (gensym))
                                (val (gensym)))
                            `(,name ,args
                                    (multiple-value-bind (,val ,ok)
                                      (gethash (list ,@args) ,table)
                                      (if ,ok ,val
                                          (setf (gethash (list ,@args) ,table)
                                                (progn ,@body)))))))
                        funcs tables)
         ,@body))))

(defmacro dpfun (name args &body body)
  (let ((f (gensym)))
    `(dplabels ((,f ,args ,@body))
       (defun ,name (&rest args)
         (apply #',f args)))))


(defun split (x str)
  (let ((pos (search x str))
        (size (length x)))
    (if pos
        (cons (subseq str 0 pos)
              (split x (subseq str (+ pos size))))
        (list str))))

(defmacro collect-times (time body)
  `(loop repeat ,time collect ,body))

(defun read-times (time)
  (collect-times time (read)))

(defmacro aif (expr then else)
  `(let ((it ,expr))
     (if it ,then ,else)))

(defmacro awhen (expr &rest then)
  `(aif ,expr (progn ,@then) nil))

(defun comulative (function list &key base)
  (if base
      (comulative function (cons base list))
      (do ((lst (cdr list) (cdr lst))
           (acc (list (car list))))
          ((null lst) (reverse acc))
        (push (funcall function (car acc) (car lst)) acc))))

(defun binary-search (function left right
                      &optional
                        (eps 1)
                        (average-function (lambda (x y) (ash (+ x y) -1))))
  (if (<= (abs (- left right)) eps)
      right
      (let ((mid (funcall average-function left right)))
        (if (funcall function mid)
            (binary-search function left mid eps average-function)
            (binary-search function mid right eps average-function)))))

(defun arithmetic-mean (&rest body)
  (/ (apply #'+ body) (length body)))

(defvar +MOD+ (+ (expt 10 9) 7))

(defun range-0-n (n &optional (step 1))
  (loop for i from 0 below n by step collect i))

(defun range-1-n (n &optional (step 1))
  (loop for i from 1 below n by step collect i))

(defun range-a-b (a b &optional (step 1))
  (loop for i from a below b by step collect i))

(defun map-0-n (function n &optional (step 1))
  (mapcar function (range-0-n n step)))

(defun map-1-n (function n &optional (step 1))
  (mapcar function (range-1-n n step)))

(defun map-a-b (function a b &optional (step 1))
  (mapcar function (range-a-b a b step)))

(defun read-string (&optional (stream *standard-input*))
  (labels ((is-empty (x)
             (or (char= x #\space) (char= x #\newline))))
    (loop for char = (read-char stream)
          with result
          when (and result (is-empty char))
            do (return (concatenate 'string (nreverse result)))
          when (null (is-empty char))
            do (push char result))))

(defun merge-sort (lst &optional (compare #'<))
  (let ((turn 0))
    (labels ((merge-list (a b a-length b-length)
               (cond ((zerop a-length) b)
                     ((zerop b-length) a)
                     ((funcall compare (car b) (car a))
                      (incf turn a-length)
                      (cons (car b)
                            (merge-list a (cdr b) a-length (1- b-length))))
                     (t
                      (cons (car a)
                            (merge-list (cdr a) b (1- a-length) b-length)))))
             (f (lst length)
               (if (= length 1)
                   lst
                   (let ((mid (ash length -1)))
                     (merge-list (f (subseq lst 0 mid) mid)
                                 (f (subseq lst mid) (- length mid))
                                 mid
                                 (- length mid))))))
      (values (f lst (length lst)) turn))))

(defun group (lst &optional (test #'eql) (key nil))
  (let ((table (make-hash-table :test test)))
    (mapc (lambda (x)
            (push x (gethash (if key (funcall key x) x) table)))
          lst)
    (loop for value being each hash-value in table
          collect value)))

(defun nearby (&rest args)
  (let ((current (subseq args 0 (ash (length args) -1)))
        (validator (subseq args (ash (length args) -1)))
        (res nil))
    (labels ((check ()
               (every (lambda (x y) (and (<= 0 x) (< x y)))
                      current validator))
             (f (lst)
               (unless lst (return-from f))
               (let ((x (car lst)))
                 (setf (car lst) (1+ x))
                 (when (check) (push (copy-list current) res))
                 (setf (car lst) (1- x))
                 (when (check) (push (copy-list current) res))
                 (setf (car lst) x))
               (f (cdr lst))))
      (f current)
      res)))

(defun make-primes (max-number)
  (let ((array (make-array (1+ max-number) :initial-element t)))
    (loop for i from 2 to max-number
          for is-prime = (aref array i)
          when is-prime collect i
          when is-prime
          do (loop for j from (* 2 i) to max-number by i
                   do (setf (aref array j) nil)))))

(defun make-is-prime (max-number)
  (let ((primes (make-primes max-number))
        (table (make-array (1+ max-number) :initial-element nil)))
    (dolist (i primes)
      (setf (aref table i) t))
    (defun is-prime (x)
      (aref table x))))


(defparameter +MOD+ (+ 7 (expt 10 9)))
(defmacro mod+ (&body args)
  (reduce (lambda (a b) `(mod (+ ,a ,b) +MOD+))
          args))
(defmacro mod- (&body args)
  (reduce (lambda (a b) `(mod (- ,a ,b) +MOD+))
          args))
(defmacro mod* (&body args)
  (reduce (lambda (a b) `(mod (* ,a ,b) +MOD+))
          args))
(defun modpow (base power)
  (if (zerop power)
      1
      (let ((base2 (mod* base base)))
        (mod* (if (oddp power) base 1)
              (modpow base2 (ash power -1))))))
(defun modinv (x)
  (modpow x (- +MOD+ 2)))
(defmacro mod/ (x &body args)
  `(mod* ,x 
         (modinv (mod* ,@args))))


(defun main (h w q query)
  (let ((ans (* h w))
	(table (make-hash-table)))
    (loop for q in query
	  for y = (car q)
	  for x = (cdr q)
	  for cy = (gethash x table (1+ h))
	  for ny = (min y cy)
	  collect (decf ans (- cy ny))
	  do (setf (gethash x table) ny))))

#-swank
(format t "~{~a~%~}"
	(let* ((h (read))
	       (w (read))
	       (q (read))
	       (query (collect-times q (cons (read) (read)))))
	  (main h w q query)))

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード