結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー | roaris |
提出日時 | 2022-10-15 02:09:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,439 ms / 6,000 ms |
コード長 | 1,364 bytes |
コンパイル時間 | 1,393 ms |
コンパイル使用メモリ | 87,128 KB |
実行使用メモリ | 185,056 KB |
最終ジャッジ日時 | 2023-09-09 01:55:35 |
合計ジャッジ時間 | 90,786 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 81 ms
71,716 KB |
testcase_01 | AC | 83 ms
71,780 KB |
testcase_02 | AC | 82 ms
71,892 KB |
testcase_03 | AC | 1,525 ms
135,528 KB |
testcase_04 | AC | 1,987 ms
154,848 KB |
testcase_05 | AC | 1,210 ms
133,768 KB |
testcase_06 | AC | 1,971 ms
150,652 KB |
testcase_07 | AC | 2,654 ms
162,836 KB |
testcase_08 | AC | 2,286 ms
151,160 KB |
testcase_09 | AC | 1,393 ms
124,028 KB |
testcase_10 | AC | 1,238 ms
118,232 KB |
testcase_11 | AC | 1,732 ms
134,740 KB |
testcase_12 | AC | 1,682 ms
135,268 KB |
testcase_13 | AC | 1,258 ms
120,340 KB |
testcase_14 | AC | 961 ms
110,424 KB |
testcase_15 | AC | 2,604 ms
165,844 KB |
testcase_16 | AC | 2,351 ms
156,864 KB |
testcase_17 | AC | 812 ms
104,916 KB |
testcase_18 | AC | 3,338 ms
183,156 KB |
testcase_19 | AC | 3,439 ms
183,592 KB |
testcase_20 | AC | 3,376 ms
184,048 KB |
testcase_21 | AC | 3,249 ms
183,580 KB |
testcase_22 | AC | 2,591 ms
183,820 KB |
testcase_23 | AC | 2,597 ms
183,408 KB |
testcase_24 | AC | 2,660 ms
183,504 KB |
testcase_25 | AC | 2,626 ms
183,280 KB |
testcase_26 | AC | 2,611 ms
183,600 KB |
testcase_27 | AC | 2,609 ms
184,264 KB |
testcase_28 | AC | 2,688 ms
184,532 KB |
testcase_29 | AC | 2,657 ms
185,056 KB |
testcase_30 | AC | 2,678 ms
184,588 KB |
testcase_31 | AC | 2,642 ms
183,800 KB |
testcase_32 | AC | 2,652 ms
184,016 KB |
testcase_33 | AC | 2,589 ms
177,448 KB |
testcase_34 | AC | 2,459 ms
177,436 KB |
testcase_35 | AC | 2,537 ms
177,052 KB |
testcase_36 | AC | 2,540 ms
177,720 KB |
testcase_37 | AC | 2,476 ms
177,288 KB |
testcase_38 | AC | 243 ms
104,620 KB |
testcase_39 | AC | 855 ms
120,152 KB |
testcase_40 | AC | 937 ms
173,476 KB |
testcase_41 | AC | 77 ms
71,636 KB |
ソースコード
import sys input = sys.stdin.readline from collections import * class BIT: def __init__(self, n): self.n = n self.bit = [0]*(n+1) def add(self, i, x): i += 1 while i<=self.n: self.bit[i] += x i += i&(-i) def update(self, i, x): self.add(i, -self.acc(i+1)+self.acc(i)) self.add(i, x) def acc(self, i): s = 0 while i>0: s += self.bit[i] i -= i&(-i) return s def get(self, l, r): return self.acc(r)-self.acc(l) N = int(input()) AT = [tuple(map(int, input().split())) for _ in range(N)] updates = [] for i in range(N): A, T = AT[i] updates.append((T-1, i, -1, A+T-1)) updates.append((T+A, i, 0, 0)) updates.sort() Q = int(input()) DLRI = [] for i in range(Q): D, L, R = map(int, input().split()) DLRI.append((D, L, R, i)) DLRI.sort() ans = [-1]*Q idx = 0 bit1 = BIT(N) bit2 = BIT(N) for i in range(N): bit2.add(i, AT[i][0]) for D, L, R, I in DLRI: while idx<2*N and updates[idx][0]<=D: bit1.update(updates[idx][1], updates[idx][2]) bit2.update(updates[idx][1], updates[idx][3]) idx += 1 a = bit1.acc(R)-bit1.acc(L-1) b = bit2.acc(R)-bit2.acc(L-1) ans[I] = a*D+b for i in range(Q): print(ans[i])