結果

問題 No.1074 増殖
コンテスト
ユーザー convexineq
提出日時 2020-06-07 03:37:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,347 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,496 KB
実行使用メモリ 102,704 KB
最終ジャッジ日時 2024-12-23 15:02:19
合計ジャッジ時間 4,934 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 8 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    
"""
C++ の std::map ぽいデータ構造
座標圧縮は前提
n: 取りうる最大値（最小値は 0）

self.dic を dict に取り換えることでメモリ節約できる
"""
class stdmap:
    def __init__(self, n):
        self.size = n+1
        self.B = BIT(n+1) #存在すれば 1、しないなら 0
        self.dic = [0]*(n+1) # 値域
    
    def insert(self,a,b): # 値 a に b を上書き
        self.B.add(a,1)
        self.dic[a] = b

    def remove(self,a): # a を取り除く
        self.B.add(a,-1)

    def lower_bound(self,k): # k 以上の最小のkeyを求める
        return self.B.bisect_left(self.B.get_sum(k))
        
    def kth_key(self,k): # k 番目に小さい元のkeyを求める
        return self.B.bisect_left(k)

    def kth_value(self,k): # k 番目に小さい元のmap先を求める
        return self.dic[self.B.bisect_left(k)]

    def prev_key(self,k): #一個前の元のkeyを求める
        idx = self.B.get_sum(k)
        assert idx != 0
        return self.B.bisect_left(idx-1)

    def next_key(self,k):
        idx = self.B.get_sum(k)
        assert idx != self.size
        return self.B.bisect_left(idx+1)

    def __getitem__(self,item):
        return self.dic[item]


# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n = int(input())
M = map(int,read().split())
xyxy = [*zip(M,M,M,M)]


def solve(xy):
    MAX = 2*10**4+10
    mp = stdmap(MAX)
    mp.insert(MAX,0)
    mp.insert(0,1<<31)

    res = [0]*n
    for i in range(n):
        x,y = xy[i]
        k = mp.lower_bound(x)
        v1 = mp[k]
        v2 = mp[mp.next_key(k)]
        if y <= v2:
            continue
        val = (y-v2)*(x-k)
        mp.insert(x,y)
        while y > v1:
            x = k
            v2 = v1
            k1 = mp.prev_key(k)
            mp.remove(k)
            k = k1
            v1 = mp[k]
            val += (y-v2)*(x-k)

        res[i] = val        
    return res


ans = [0]*n
res1 = solve([(x2,y2) for x1,y1,x2,y2 in xyxy])
res2 = solve([(-x1,y2) for x1,y1,x2,y2 in xyxy])
res3 = solve([(x2,-y1) for x1,y1,x2,y2 in xyxy])
res4 = solve([(-x1,-y1) for x1,y1,x2,y2 in xyxy])
for i in range(n):
    ans[i] += res1[i]+res2[i]+res3[i]+res4[i]
print("\n".join(map(str,ans)))
0