結果

問題 No.877 Range ReLU Query
ユーザー neterukunneterukun
提出日時 2019-09-06 22:40:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,113 ms / 2,000 ms
コード長 1,935 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 111,172 KB
最終ジャッジ日時 2024-11-08 10:08:23
合計ジャッジ時間 12,471 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
52,608 KB
testcase_01 AC 92 ms
71,808 KB
testcase_02 AC 81 ms
71,168 KB
testcase_03 AC 101 ms
76,416 KB
testcase_04 AC 52 ms
59,904 KB
testcase_05 AC 73 ms
66,688 KB
testcase_06 AC 77 ms
68,096 KB
testcase_07 AC 68 ms
65,152 KB
testcase_08 AC 100 ms
76,160 KB
testcase_09 AC 54 ms
60,416 KB
testcase_10 AC 86 ms
71,552 KB
testcase_11 AC 1,023 ms
109,716 KB
testcase_12 AC 915 ms
110,116 KB
testcase_13 AC 746 ms
99,212 KB
testcase_14 AC 788 ms
100,012 KB
testcase_15 AC 1,109 ms
110,304 KB
testcase_16 AC 1,039 ms
108,076 KB
testcase_17 AC 1,113 ms
111,172 KB
testcase_18 AC 1,037 ms
108,348 KB
testcase_19 AC 1,007 ms
110,108 KB
testcase_20 AC 1,068 ms
110,612 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from operator import itemgetter 


class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: i番目をvalに変更する
    get_sum: 区間[begin, end)の和を求める
    """
    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = self.node[2*i + 1] + self.node[2*i + 2]

    def get_sum(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = 0
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = s + self.node[end]
            if (begin - 1) & 1:
                s = s + self.node[begin]
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s


n, q = map(int, input().split())
a = list(map(int, input().split()))
info = [[i] + list(map(int, input().split())) for i in range(q)]

ruiseki = [0]*(n+1)
for i in range(n):
    ruiseki[i+1] = ruiseki[i] + a[i]

st = SegmentTree(n)
st_cnt = SegmentTree(n)

a = sorted(zip(a, range(len(a))))
info = sorted(info, key = itemgetter(4))

minus = 0
ind = 0
ans = []
for i in range(q):
    j, _, l, r, val = info[i]
    if minus < val:
        minus = val
        while True:
            if ind == n:
                break
            if a[ind][0] <= minus:
                st.update(a[ind][1], a[ind][0])
                st_cnt.update(a[ind][1], 1)
                ind += 1
            else:
                break
    ans.append((j, (ruiseki[r] - ruiseki[l-1]) - st.get_sum(l-1, r) - minus * (r-l+1-st_cnt.get_sum(l-1, r))))
ans = sorted(ans)
for i in range(q):
    print(ans[i][1])
0