結果

問題 No.1074 増殖
コンテスト
ユーザー tpyneriver
提出日時 2020-06-05 22:48:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 6,223 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 115,076 KB
最終ジャッジ日時 2024-12-17 16:59:39
合計ジャッジ時間 7,375 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from operator import add
readline = sys.stdin.readline

class Lazysegtree:
    #RUQ
    def __init__(self, A, intv, initialize = True, segf = add):
        #区間は 1-indexed で管理
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        self.lazy = [None]*(2*self.N0)
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, -1, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)

    def __repr__(self):
        return str([self.query(i, i+1) for i in range(self.N)])

    
    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1])
            
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            if self.lazy[idx] is None:
                continue
            self.data[2*idx] = self.data[2*idx+1] = self.lazy[2*idx] \
            = self.lazy[2*idx+1] = self.lazy[idx] 
            self.lazy[idx] = None
            
            
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        self._descend(L//(L & -L))
        self._descend(R//(R & -R)-1)
        
        s = self.intv                                                                   

        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def update(self, l, r, x):
        L = l+self.N0
        R = r+self.N0

        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri-1)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data[R] = x
                self.lazy[R] = x
            if L & 1:
                self.data[L] = x
                self.lazy[L] = x
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
    
    def __repr__(self):
        return str([self.query(i, i+1) for i in range(self.N)])
    
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx - self.N0
        else:
            pre = self.data[l+self.N0]
            for idx in (SL + SR[::-1]):
                if not check(self.segf(pre, self.data[idx])):
                    pre = self.segf(pre, self.data[idx])
                else:
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.segf(pre, self.data[2*idx])):
                    idx = 2*idx
                else:
                    pre = self.segf(pre, self.data[2*idx])
                    idx = 2*idx + 1
            return idx - self.N0

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

def calc(Ax, Ay):
    N = len(Ax)
    Lx, Cx = compress(Ax)
    Lx.append(0)
    table = Segtree([None]*(N+2), 0, initialize = False, segf = max)
    T = Lazysegtree([None]*(N+2), 0, initialize = False)
    N0 = T.N0
    ans = [0]*N
    for i in range(N):
        x, y = Ax[i], Ay[i]
        xidx = Cx[x]
        mt = table.query(xidx, N0)
        if mt >= y:
            ans[i] = ans[i-1]
            continue
        pidx = table.binsearch(0, xidx, lambda x: x > y, reverse = True) + 1
        table.update(xidx, y)
        midx = table.binsearch(xidx+1, N0, lambda x: x == mt)
        #print(table)
        #print(i, pidx, xidx, midx, mt)
        T.update(pidx, xidx+1, 0)
        T.update(xidx, xidx+1, (Lx[xidx] - Lx[pidx-1])*y)
        T.update(midx, midx+1, (Lx[midx] - Lx[xidx])*mt)
        #print('T', T)
        ans[i] = T.query(0, N0)
    return ans


N = int(readline())
XaYaXbYb = [tuple(map(int, readline().split())) for _ in range(N)]
Xa, Ya, Xb, Yb = map(list, zip(*XaYaXbYb))
Xa = [-x for x in Xa]
Ya = [-y for y in Ya]
Ans = [0]*N
ans1 = calc(Xb, Yb)
ans2 = calc(Xb, Ya)
ans3 = calc(Xa, Yb)
ans4 = calc(Xa, Ya)
for i in range(N):
    Ans[i] = ans1[i] + ans2[i] + ans3[i] + ans4[i]

Ans = [0] + Ans
Ans = [a2 - a1 for a1, a2 in zip(Ans, Ans[1:])]
print('\n'.join(map(str, Ans)))
#print(ans1, ans2, ans3, ans4)
0