blob: e90f2425e6cff67cf92e9624fea5c936e0d42482 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
(define (read-table m n)
(define (read-row n)
(if (= n 0)
'()
(cons (read)
(read-row (- n 1)))))
(if (= m 0)
'()
(cons (read-row n)
(read-table (- m 1) n))))
(define (accumulate-n op last seqs)
(define (accumulate op last sequence)
(if (null? sequence)
last
(op (car sequence)
(accumulate op last (cdr sequence)))))
(if (null? (car seqs))
'()
(cons (accumulate op last (map car seqs))
(accumulate-n op last (map cdr seqs)))))
(define (remove-duplicates sequence)
(if (< (length sequence) 2)
sequence
(let ((a (car sequence))
(d (remove-duplicates (cdr sequence))))
(if (= a (car d)) d (cons a d)))))
(define (lol-to-vos matrix cmp)
(list->vector (map (lambda (lst)
(list->vector (remove-duplicates (sort lst cmp))))
matrix)))
; Since we're sure that val is in vec, no need to check if low > high.
(define (binary-search vec cmp val low high)
(let* ((mid (floor (/ (+ high low) 2)))
(n (vector-ref vec mid)))
(cond ((= n val) mid)
((cmp n val) (binary-search vec cmp val (+ mid 1) high))
(else (binary-search vec cmp val low (- mid 1))))))
(define (make-lov m n)
(if (= m 0)
'()
(cons (make-vector n 0)
(make-lov (- m 1) n))))
(define (exact m n a r c e)
(define (iter i j)
(let ((val (vector-ref (vector-ref a i) j))
(row (vector-ref r i))
(col (vector-ref c j)))
(let ((alphas (vector-ref e (binary-search row < val 0 (vector-length row))))
(beta (binary-search col > val 0 (vector-length col))))
(vector-set! alphas beta (+ (vector-ref alphas beta) 1))))
(cond ((and (= i m) (= j n)) e)
((= j n) (iter (+ i 1) 0))
(else (iter i (+ j 1)))))
(iter 0 0))
(define (all-rows matrix m n)
(define (all-row row)
(define (iter i)
(if (< i (- n 1))
(let ((j (+ i 1)))
(vector-set! row j (+ (vector-ref row i)
(vector-ref row j)))
(iter j))))
(iter 0))
(let ((i (- m 1)))
(all-row (vector-ref matrix i))
(if (> i 0) (all-rows matrix i n))))
(define (all matrix m n)
(define (iter i j)
(let ((row (vector-ref matrix i))
(l (- i 1)))
(vector-set! row j (+ (vector-ref row j)
(vector-ref (vector-ref matrix l) j))))
(cond ((and (= i m) (= j n)))
((= j n) (iter (+ i 1) 0))
(else (iter i (+ j 1)))))
(if (> m 0) (iter 1 0)))
(define (answer e m n k)
(if (> k 0)
(let* ((a ((lambda (x) (if (= x m) (- x 1) x)) (read)))
(b ((lambda (x) (if (= x n) (- x 1) x)) (read))))
(display (vector-ref (vector-ref e a) b))
(newline)
(answer e m n (- k 1)))))
(with-input-from-file "MAB.INP"
(lambda ()
(with-output-to-file "MAB.OUT"
(lambda ()
(let* ((m (read))
(n (read))
(k (read))
(a (read-table m n))
(e (exact (- m 1)
(- n 1)
(list->vector (map list->vector a))
(lol-to-vos a <)
(lol-to-vos (accumulate-n cons '() a) >)
(list->vector (make-lov m n)))))
(all-rows e m n)
(all e (- m 1) (- n 1))
(answer e m n k))))))
|
