#931126 (PyPy3) No.2543 Many Meetings

提出ソース

結果

問題	No.2543 Many Meetings
ユーザー	flygon
提出日時	2023-11-24 22:29:35
言語	PyPy3 (7.3.15)
結果	RE
実行時間	-
コード長	5,276 bytes
コンパイル時間	371 ms
コンパイル使用メモリ	81,700 KB
実行使用メモリ	269,000 KB
最終ジャッジ日時	2023-11-24 22:29:49
合計ジャッジ時間	13,344 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	44 ms 55,724 KB
testcase_01	AC	45 ms 55,724 KB
testcase_02	AC	46 ms 55,724 KB
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	TLE	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
sys.setrecursionlimit(5*10**5)
input = sys.stdin.readline
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
from math import gcd
def add(x, y):
    return x + y


def e(a):
    if a == min:
        return 10**18
    if a == max:
        return -10**18
    if a == add:
        return 0


class SegTree:
    def __init__(self, segf, init_val):
        n = len(init_val)
        self.segf = segf
        self.e = e(segf)
        self.seg_len = 1 << n.bit_length()
        self.seg = [self.e] * (self.seg_len<<1)

    def point_add(self, pos, x):
        pos += self.seg_len
        self.seg[pos] += x
        while True:
            pos >>= 1
            if not pos:
                break
            self.seg[pos] = self.segf(
                self.seg[pos << 1],  self.seg[pos << 1 | 1])

    def point_update(self, pos, x):
        pos += self.seg_len
        self.seg[pos] = self.segf(self.seg[pos], x)
        while True:
            pos >>= 1
            if not pos:
                break
            self.seg[pos] = self.segf(
                self.seg[pos << 1],  self.seg[pos << 1 | 1])

    def get_range(self, l, r):
        l += self.seg_len
        r += self.seg_len
        res = self.e
        while l < r:
            if l & 1:
                res = self.segf(res, self.seg[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.segf(res, self.seg[r])
            l >>= 1
            r >>= 1
        return res
    

    # max_rightをもとめるための条件式
    def j(self, now, i, t):
        return self.segf(now, self.seg[i]) >= t
    
    # 区間内で条件を満たせない場合-1を返す
    # そうでない場合[ql,ans)が条件を満たすような最右のansを返す
    def max_right(self,ql,qr,t):
        l = ql + self.seg_len
        r = qr + self.seg_len
        if not self.j(self.e, l, t): return -1
        left = []
        right = []
        while l < r:
            if l & 1:left.append(l); l += 1
            if r & 1:r -= 1; right.append(r)
            l >>= 1; r >>= 1
        ord = left + right[::-1]
        now = self.e
        pos = -1
        for i in ord:
            if self.j(now, i, t):
                now = self.segf(now, self.seg[i])
            else:
                pos = i
                break
        if pos == -1:return qr
        while True:
            if pos >= self.seg_len:break
            pos <<= 1
            if self.j(now, pos, t):
                now = self.segf(now, self.seg[pos])
                pos += 1
        return pos - self.seg_len
    
    # 区間内で条件を満たせない場合-1を返す
    # そうでない場合(ans,qr)が条件を満たすような最左のansを返す
    def min_left(self,ql,qr,t):
        l = ql + self.seg_len
        r = qr + self.seg_len
        if not self.j(self.e, r-1, t): return -1
        left = []
        right = []
        while l < r:
            if l & 1:left.append(l); l += 1
            if r & 1:r -= 1; right.append(r)
            l >>= 1; r >>= 1
        ord = left + right[::-1]
        now = self.e
        pos = -1
        for i in ord[::-1]:
            if self.j(now, i, t):
                now = self.segf(now, self.seg[i])
            else:
                pos = i
                break
        if pos == -1:return ql-1
        while True:
            if pos >= self.seg_len:break
            pos = (pos<<1) + 1
            if self.j(now, pos, t):
                now = self.segf(now, self.seg[pos])
                pos -= 1
        return pos - self.seg_len

    # ------ dual -------
    def range_add(self, l, r, x):
        l += self.seg_len
        r += self.seg_len
        while l < r:
            if l & 1:
                self.seg[l] = self.segf(x, self.seg[l])
                l += 1
            if r & 1:
                r -= 1
                self.seg[r] = self.segf(x, self.seg[r])
            l >>= 1
            r >>= 1

    def get_point(self, pos):
        pos += self.seg_len
        res = self.seg[pos]
        while True:
            pos >>= 1
            if not pos:
                break
            res = self.segf(res, self.seg[pos])
        return res

n,k = map(int,input().split())

lr = [list(map(int,input().split())) for i in range(n)]

c = 10**9+10
d = []
all = [lr]
for i in range(3):
    st = SegTree(min, [0]*(2*len(lr)+10))
    s = set()
    for j in range(len(lr)):
        s.add(lr[j][0])
        s.add(lr[j][1])
    d = dict()
    s = sorted(s)
    for i in range(len(s)):
        d[s[i]] = i
    for i in range(len(lr)):
        st.point_update(d[lr[i][0]], lr[i][1])
    new = []
    for i in range(len(lr)):
        l,r = lr[i]        
        new.append([l, st.get_range(d[r], 2*len(lr)+5)])
    all.append(new)
    lr = new

use = []
now = 0
while k:
    if k % 2:
        use.append(now)
    k //= 2
    now += 1

ans = 10**15
for i in range(len(all[use[0]])):
    l,r = all[use[0]][i]
    lastr = r
    for j in use[1:]:
        mnr = 10**15
        for ll, rr in all[j]:
            if ll >= lastr:
                mnr = min(mnr, rr)
        lastr = mnr
    ans = min(ans, lastr-l)

print(ans) if ans <= 10**9+10 else print(-1)

yukicoder

結果

テストケース

ソースコード