結果

問題 No.878 Range High-Element Query
コンテスト
ユーザー chineristAC
提出日時 2020-10-26 12:22:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,091 bytes
記録
コンパイル時間 348 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 109,696 KB
最終ジャッジ日時 2024-07-21 21:19:51
合計ジャッジ時間 7,048 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class SegmentTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.range = [(-1,n)] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
            self.range[self.num + i] = (i,i)
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
            self.range[i] = (self.range[2 * i][0],self.range[2 * i + 1][1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            if not k%2:
                self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            else:
                self.tree[k >> 1] = self.segfunc(self.tree[k ^ 1], self.tree[k])
            k >>= 1

    def query(self,l,r):
        l+=self.num
        r+=self.num
        res=self.ide_ele
        L = []
        R = []
        while l<r:
            if l&1:
                L.append(l)
                l+=1
            if r&1:
                R.append(r-1)
            l>>=1
            r>>=1

        if L and R and R[-1]==L[-1]:
            R.pop()
        R=R[::-1]
        m = L+R
        for idx in m:
            res = self.segfunc(res,self.tree[idx])
        return res

def segfunc(x,y):
    if x[0]<=y[0]:
        return (y[0],x[1]+y[1])
    else:
        return x

ide_ele = (0,0)

import sys

input = sys.stdin.readline

N,Q = map(int,input().split())
a = list(map(int,input().split()))
a = [(a[i],1) for i in range(N)]
Seg = SegmentTree(a,segfunc,ide_ele)

query = [list(map(int,input().split()))+[i] for i in range(Q)]
ans = [-1 for i in range(Q)]
query.sort(key=lambda x:-x[1])

pos = 0
while query:
    a,l,r,idx = query.pop()
    while l-1>pos:
        Seg.update(pos,(0,0))
        pos += 1
    ans[idx] = Seg.query(l-1,r)[1]

for i in range(Q):
    print(ans[i])
0