結果

問題 No.1074 増殖
コンテスト
ユーザー Kiri8128
提出日時 2020-05-17 03:59:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,416 ms / 2,000 ms
コード長 5,245 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 103,780 KB
最終ジャッジ日時 2024-09-24 09:23:50
合計ジャッジ時間 9,218 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = lambda: sys.stdin.readline().rstrip()
class Segtree():
    def __init__(self, nn, A = []):
        self.inf = 10 ** 9
        self.size = 1 << nn
        n = self.size * 2
        self.S = [0] * n
        self.ma = [0] * n
        self.mi = [0] * n
        self.mac = [1] * n
        self.mic = [1] * n
        self.sma = [-self.inf] * n
        self.smi = [self.inf] * n
        self.lazy = [0] * n
        for i, a in enumerate(A):
            self.node_set(i, a)
        for i in range(len(A), self.size):
            self.node_set(i, 0)
        self.update_all()

    def node_chmax(self, i, x):
        self.S[i] += (x - self.ma[i]) * self.mac[i]
        if self.ma[i] == self.mi[i]:
            self.ma[i] = x
            self.mi[i] = x
        elif self.ma[i] == self.smi[i]:
            self.ma[i] = x
            self.smi[i] = x
        else:
            self.ma[i] = x
    
    def node_chmin(self, i, x):
        self.S[i] += (x - self.mi[i]) * self.mic[i]
        if self.ma[i] == self.mi[i]:
            self.ma[i] = x
            self.mi[i] = x
        elif self.sma[i] == self.mi[i]:
            self.sma[i] = x
            self.mi[i] = x
        else:
            self.mi[i] = x
    
    def node_set(self, i, x):
        i += self.size
        self.ma[i] = x
        self.mi[i] = x
        self.S[i] = x
    
    def update_all(self):
        for i in range(self.size - 1, 0, -1):
            self.update(i)
    
    def update(self, i):
        c1 = i * 2
        c2 = c1 | 1
        self.S[i] = self.S[c1] + self.S[c2]
        if self.ma[c1] < self.ma[c2]:
            self.ma[i] = self.ma[c2]
            self.mac[i] = self.mac[c2]
            self.sma[i] = max(self.ma[c1], self.sma[c2])
        elif self.ma[c1] > self.ma[c2]:
            self.ma[i] = self.ma[c1]
            self.mac[i] = self.mac[c1]
            self.sma[i] = max(self.sma[c1], self.ma[c2])
        else:
            self.ma[i] = self.ma[c1]
            self.mac[i] = self.mac[c1] + self.mac[c2]
            self.sma[i] = max(self.sma[c1], self.sma[c2])
        
        if self.mi[c1] < self.mi[c2]:
            self.mi[i] = self.mi[c1]
            self.mic[i] = self.mic[c1]
            self.smi[i] = min(self.smi[c1], self.mi[c2])
        elif self.mi[c1] > self.mi[c2]:
            self.mi[i] = self.mi[c2]
            self.mic[i] = self.mic[c2]
            self.smi[i] = min(self.mi[c1], self.smi[c2])
        else:
            self.mi[i] = self.mi[c1]
            self.mic[i] = self.mic[c1] + self.mic[c2]
            self.smi[i] = min(self.smi[c1], self.smi[c2])
    
    def range_sum(self, a, b, i=1, l=0, r=-1):
        if r == -1: r = self.size
        if r <= a or b <= l: return 0
        if a <=l and r <= b: return self.S[i]
        self.push(i, r - l)
        return self.range_sum(a, b, i * 2, l, (l + r) // 2) + self.range_sum(a, b, i * 2 | 1, (l + r) // 2, r)
    
    def push(self, i, le):
        if i >= self.size: return
        c1 = i * 2
        c2 = c1 | 1
        if self.lazy[i] != 0:
            self.node_add(c1, le // 2, self.lazy[i])
            self.node_add(c2, le // 2, self.lazy[i])
            self.lazy[i] = 0
        if self.ma[c1] > self.ma[i]: self.node_chmax(c1, self.ma[i])
        if self.ma[c2] > self.ma[i]: self.node_chmax(c2, self.ma[i])
        if self.mi[c1] < self.mi[i]: self.node_chmin(c1, self.mi[i])
        if self.mi[c2] < self.mi[i]: self.node_chmin(c2, self.mi[i])
    
    def node_add(self, i, le, x):
        self.ma[i] += x
        if self.sma[i] != - self.inf:
            self.sma[i] += x
        self.mi[i] += x
        if self.smi[i] != self.inf:
            self.smi[i] += x
        self.S[i] += x * le
        self.lazy[i] += x
    
    def range_chmax(self, a, b, x, i=1, l=0, r=-1):
        if r == -1: r = self.size
        if r <= a or b <= l or self.mi[i] >= x: return
        if a <= l and r <= b and self.smi[i] > x:
            self.node_chmin(i, x)
            return
        self.push(i, r - l)
        self.range_chmax(a, b, x, i * 2, l, (l + r) // 2)
        self.range_chmax(a, b, x, i * 2 | 1, (l + r) // 2, r)
        self.update(i)
    
    def range_chmin(self, a, b, x, i=1, l=0, r=-1):
        if r == -1: r = self.size
        if r <= a or b <= l or self.ma[i] <= x: return
        if a <= l and r <= b and self.sma[i] < x:
            self.node_chmax(i, x)
            return
        self.push(i, r - l)
        self.range_chmin(a, b, x, i * 2, l, (l + r) // 2)
        self.range_chmin(a, b, x, i * 2 | 1, (l + r) // 2, r)
        self.update(i)
    
    def range_add(self, a, b, x, i=1, l=0, r=-1):
        if r == -1: r = self.size
        if r <= a or b <= l: return
        if a <= l and r <= b:
            self.node_add(i, r - l, x)
            return
        self.push(i, r - l)
        self.range_add(a, b, x, 2 * i, l, (l + r) // 2)
        self.range_add(a, b, x, 2 * i | 1, (l + r) // 2, r)
        self.update(i)
    
N = int(input())
st = Segtree(17)
pre = 0
ANS = []
for _ in range(N):
    xa, ya, xb, yb = map(int, input().split())
    st.range_chmax(xa + 20000, xb + 20000, yb)
    st.range_chmax(xa + 70000, xb + 70000, -ya)
    s = st.range_sum(0, 1 << 17)
    ANS.append(s - pre)
    pre = s
print("\n".join(map(str, ANS)))
0