結果
問題 | No.738 平らな農地 |
ユーザー | rlangevin |
提出日時 | 2024-02-07 12:23:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 384 ms / 2,000 ms |
コード長 | 1,809 bytes |
コンパイル時間 | 501 ms |
コンパイル使用メモリ | 81,572 KB |
実行使用メモリ | 100,692 KB |
最終ジャッジ日時 | 2024-02-07 12:24:15 |
合計ジャッジ時間 | 23,255 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
55,736 KB |
testcase_01 | AC | 41 ms
55,736 KB |
testcase_02 | AC | 42 ms
55,736 KB |
testcase_03 | AC | 43 ms
55,736 KB |
testcase_04 | AC | 42 ms
55,736 KB |
testcase_05 | AC | 111 ms
77,404 KB |
testcase_06 | AC | 111 ms
77,428 KB |
testcase_07 | AC | 114 ms
78,748 KB |
testcase_08 | AC | 96 ms
76,508 KB |
testcase_09 | AC | 67 ms
72,196 KB |
testcase_10 | AC | 57 ms
65,888 KB |
testcase_11 | AC | 86 ms
76,248 KB |
testcase_12 | AC | 68 ms
72,084 KB |
testcase_13 | AC | 109 ms
77,472 KB |
testcase_14 | AC | 76 ms
75,532 KB |
testcase_15 | AC | 305 ms
91,016 KB |
testcase_16 | AC | 308 ms
93,360 KB |
testcase_17 | AC | 331 ms
93,596 KB |
testcase_18 | AC | 356 ms
91,892 KB |
testcase_19 | AC | 357 ms
93,824 KB |
testcase_20 | AC | 312 ms
93,352 KB |
testcase_21 | AC | 384 ms
93,328 KB |
testcase_22 | AC | 312 ms
93,356 KB |
testcase_23 | AC | 340 ms
93,520 KB |
testcase_24 | AC | 351 ms
93,880 KB |
testcase_25 | AC | 70 ms
73,096 KB |
testcase_26 | AC | 76 ms
75,540 KB |
testcase_27 | AC | 79 ms
75,540 KB |
testcase_28 | AC | 69 ms
73,092 KB |
testcase_29 | AC | 78 ms
75,544 KB |
testcase_30 | AC | 77 ms
75,540 KB |
testcase_31 | AC | 70 ms
72,972 KB |
testcase_32 | AC | 68 ms
72,324 KB |
testcase_33 | AC | 77 ms
75,400 KB |
testcase_34 | AC | 69 ms
72,708 KB |
testcase_35 | AC | 70 ms
72,084 KB |
testcase_36 | AC | 68 ms
72,340 KB |
testcase_37 | AC | 71 ms
73,112 KB |
testcase_38 | AC | 78 ms
75,532 KB |
testcase_39 | AC | 77 ms
75,536 KB |
testcase_40 | AC | 77 ms
75,544 KB |
testcase_41 | AC | 78 ms
75,524 KB |
testcase_42 | AC | 67 ms
72,088 KB |
testcase_43 | AC | 66 ms
72,068 KB |
testcase_44 | AC | 68 ms
72,452 KB |
testcase_45 | AC | 312 ms
94,808 KB |
testcase_46 | AC | 335 ms
92,736 KB |
testcase_47 | AC | 315 ms
95,352 KB |
testcase_48 | AC | 291 ms
95,140 KB |
testcase_49 | AC | 294 ms
93,212 KB |
testcase_50 | AC | 329 ms
94,568 KB |
testcase_51 | AC | 323 ms
94,452 KB |
testcase_52 | AC | 309 ms
93,980 KB |
testcase_53 | AC | 309 ms
95,184 KB |
testcase_54 | AC | 345 ms
95,368 KB |
testcase_55 | AC | 320 ms
94,456 KB |
testcase_56 | AC | 313 ms
95,204 KB |
testcase_57 | AC | 304 ms
92,728 KB |
testcase_58 | AC | 308 ms
94,420 KB |
testcase_59 | AC | 308 ms
94,792 KB |
testcase_60 | AC | 301 ms
94,772 KB |
testcase_61 | AC | 331 ms
94,764 KB |
testcase_62 | AC | 317 ms
92,368 KB |
testcase_63 | AC | 320 ms
94,800 KB |
testcase_64 | AC | 317 ms
94,740 KB |
testcase_65 | AC | 376 ms
96,564 KB |
testcase_66 | AC | 346 ms
93,792 KB |
testcase_67 | AC | 270 ms
97,604 KB |
testcase_68 | AC | 301 ms
100,576 KB |
testcase_69 | AC | 348 ms
99,912 KB |
testcase_70 | AC | 321 ms
99,884 KB |
testcase_71 | AC | 263 ms
91,428 KB |
testcase_72 | AC | 274 ms
90,472 KB |
testcase_73 | AC | 233 ms
91,852 KB |
testcase_74 | AC | 260 ms
91,972 KB |
testcase_75 | AC | 305 ms
97,684 KB |
testcase_76 | AC | 310 ms
100,692 KB |
testcase_77 | AC | 336 ms
97,104 KB |
testcase_78 | AC | 335 ms
99,860 KB |
testcase_79 | AC | 336 ms
99,928 KB |
testcase_80 | AC | 323 ms
99,952 KB |
testcase_81 | AC | 315 ms
99,432 KB |
testcase_82 | AC | 333 ms
99,740 KB |
testcase_83 | AC | 292 ms
91,640 KB |
testcase_84 | AC | 262 ms
91,776 KB |
testcase_85 | AC | 377 ms
99,604 KB |
testcase_86 | AC | 358 ms
97,260 KB |
testcase_87 | AC | 242 ms
98,920 KB |
testcase_88 | AC | 211 ms
97,096 KB |
testcase_89 | AC | 41 ms
55,736 KB |
testcase_90 | AC | 41 ms
55,736 KB |
testcase_91 | AC | 42 ms
55,736 KB |
ソースコード
class Fenwick_Tree: def __init__(self, n): self._n = n self.data = [0] * n def add(self, p, x): assert 0 <= p < self._n p += 1 while p <= self._n: self.data[p - 1] += x p += p & -p def sum(self, l, r): assert 0 <= l <= r <= self._n return self._sum(r) - self._sum(l) def _sum(self, r): s = 0 while r > 0: s += self.data[r - 1] r -= r & -r return s def get(self, k): k += 1 x, r = 0, 1 while r < self._n: r <<= 1 len = r while len: if x + len - 1 < self._n: if self.data[x + len - 1] < k: k -= self.data[x + len - 1] x += len len >>= 1 return x from bisect import * from copy import * def compress(lst): B = [] D = dict() vals = deepcopy(lst) vals = list(set(vals)) vals.sort() for i in range(len(lst)): ind = bisect_left(vals, lst[i]) B.append(ind) for i in range(len(B)): D[lst[i]] = B[i] return B, D, vals N, K = map(int, input().split()) A = list(map(int, input().split())) + [-1] A, _, itov = compress(A) Ts = Fenwick_Tree(N + 5) Tn = Fenwick_Tree(N + 5) for i in range(K): Ts.add(A[i], itov[A[i]]) Tn.add(A[i], 1) ind = Tn.get(K//2) ans = Ts.sum(ind + 1, N + 5) - Ts.sum(0, ind) + itov[ind] * (Tn.sum(0, ind) - Tn.sum(ind+1, N + 5)) for i in range(K, N): Ts.add(A[i-K], -itov[A[i-K]]) Ts.add(A[i], itov[A[i]]) Tn.add(A[i-K], -1) Tn.add(A[i], 1) ind = Tn.get(K//2) val = itov[ind] ans = min(ans, Ts.sum(ind + 1, N + 5) - Ts.sum(0, ind) + val * (Tn.sum(0, ind) - Tn.sum(ind+1, N + 5))) print(ans)