結果

問題 No.2543 Many Meetings
コンテスト
ユーザー flygon
提出日時 2023-11-24 22:39:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,371 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 278,112 KB
最終ジャッジ日時 2024-09-26 09:40:03
合計ジャッジ時間 19,809 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other RE * 13 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
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)]

use = []
now = 0
while k:
    if k % 2:
        use.append(now)
    k //= 2
    now += 1
c = 10**9+10
d = []
all = [lr]
for i in range(20):
    s = set()
    for j in range(len(lr)):
        s.add(lr[j][0])
        s.add(lr[j][1])
    st = SegTree(min, [0]*(len(s)+10))
    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


# ans = 10**15
# rs = set()
# for i in use:
#     for l,r in all[i]:
#         rs.add()
# 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)
0