#835267 (Python3) No.2197 Same Dish

提出ソース

結果

問題	No.2197 Same Dish
ユーザー	faculty_of_900
提出日時	2023-01-24 22:22:20
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	1,404 ms / 2,000 ms
コード長	10,819 bytes
コンパイル時間	114 ms
コンパイル使用メモリ	13,696 KB
実行使用メモリ	28,392 KB
最終ジャッジ日時	2024-06-26 07:38:31
合計ジャッジ時間	11,664 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	49 ms 13,696 KB
testcase_01	AC	50 ms 13,824 KB
testcase_02	AC	50 ms 13,696 KB
testcase_03	AC	52 ms 13,824 KB
testcase_04	AC	51 ms 13,824 KB
testcase_05	AC	50 ms 13,568 KB
testcase_06	AC	50 ms 13,696 KB
testcase_07	AC	50 ms 13,824 KB
testcase_08	AC	51 ms 13,824 KB
testcase_09	AC	49 ms 13,824 KB
testcase_10	AC	49 ms 13,568 KB
testcase_11	AC	49 ms 13,696 KB
testcase_12	AC	51 ms 13,696 KB
testcase_13	AC	136 ms 15,744 KB
testcase_14	AC	1,021 ms 26,568 KB
testcase_15	AC	1,174 ms 27,996 KB
testcase_16	AC	669 ms 23,352 KB
testcase_17	AC	579 ms 21,632 KB
testcase_18	AC	1,219 ms 28,392 KB
testcase_19	AC	1,211 ms 28,132 KB
testcase_20	AC	1,231 ms 28,260 KB
testcase_21	AC	1,404 ms 28,136 KB
testcase_22	AC	681 ms 28,264 KB

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

ソースコード

raw source code

# ライブラリインポート------------------------------------------
import math
import collections
#import statistics
from copy import deepcopy
from collections import defaultdict,deque
from sys import exit,setrecursionlimit
from heapq import heapify,heappush,heappop
from bisect import bisect_left,bisect_right,insort
from itertools import product,permutations,combinations,accumulate,combinations_with_replacement
from decimal import Decimal
#from numpy import array,matrix,dot,T
from functools import lru_cache
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
from string import ascii_uppercase, ascii_lowercase

# お決まり------------------------------------------------
INF=10**18  # まれに足りない場合もある
MOD=10**9+7
mod=998244353
def YesNo(b): print("Yes") if b else print("No")
def YESNO(b): print("YES") if b else print("NO")
dxy4=[(1,0),(-1,0),(0,1),(0,-1)]
dxy8=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]
ALPHA=ascii_uppercase
alpha=ascii_lowercase
setrecursionlimit(2*10**5)
def PrintHW(array,hight,width):
    for i in range(hight): print(*array[i][:width])
def sortx(array,num): return sorted(array, key=lambda x:x[num])
def sortxr(array,num): return sorted(array, key=lambda x:x[num], reverse=True)
def LL(h,w,e=0): return [[e for i in range(w)] for j in range(h)]
def LLL(a,b,c,e=0): return [LL(b,c,e) for _ in range(a)]
def LLLL(a,b,c,d,e=0): return [LLL(b,c,d,e) for _ in range(a)]
def DD(): return defaultdict(int)  # 初期値指定ならdefaultdict(lambda: 1)などとする
def LB(n): return [[] for _ in range(n)]
def Dc(x): return Decimal(str(x))
#@lru_cache(maxsize=2*10**5)

# 入力----------------------------------------------------
def II(): return int(input())
def MI(): return map(int, input().split())
def TI(): return tuple(map(int, input().split()))
def LI(): return list(MI())
def SLI(): return sorted(LI())
def MS(): return map(str, input().split())
def LS(): return list(MS())
def LLI(rows): return [LI() for _ in range(rows)]
def LLS(rows): return [list(input()) for _ in range(rows)]
def Graph0(vertex,edge,LLI):
    ret=[[] for _ in range(vertex)]
    for [u,v] in LLI:
        u-=1; v-=1;  # 消す場合もあり
        ret[u].append(v); ret[v].append(u);
    return ret
def Banhei(hight,width,LLS,wall='#'):  # 01マップなら0
    ret=[[wall]*(width+2)]
    for i in range(hight):
        ret.append([wall]+LLS[i]+[wall])
    ret.append([wall]*(width+2))
    return ret
def MLI(n):  # [A,B] = MLI(N)のように使う
    arr=LLI(n); l=len(arr[0])
    ret=[[] for _ in range(l)]
    for i in range(n):
        for j in range(l): ret[j].append(arr[i][j])
    return ret
def ALLI():  # 何個与えられるかわからないとき
    res=[]
    while True:
        try: res.append(LI())
        except: break
    return res

# 出力カンペ--------------------------------------------
"""
print(''.join(['a', 'b', 'c'])) # abc
print("{:b}".format(b)) # 1100101010  2進数表記 
print("{:o}".format(b)) # 1452        8進数表記
print("{:x}".format(b)) # 32a         16進数小文字表記
print("{:X}".format(b)) # 32A         16進数大文字表記
print("python".ljust(15,'-')) # 左詰め python---------
print("python".center(15,'-'))# 中寄せ -----python----
print("python".rjust(15,'-')) # 右詰め ---------python
print(str(29).rjust(10,'0')) # 10桁ゼロ埋め 0000000029
print("{:.8f}".format(a/b)) # 小数点以下の桁数指定表示
N='aiueokakikukeko'
N=N.translate(str.maketrans({'a':'A'}))  #N = AiueokAkikukeko
"""

# 頻出ツール------------------------------------------
def acc(A):
    # 配列Aの累積和、最初に0を追加する。
    return [0] + list(accumulate(A))
def acc2d(A,H,W):
    # サイズH*Wの2次元配列Aの2次元累積和。先頭に0を挿入。
    B=LL(H+1,W+1)
    for x in range(H):
        for y in range(W):
            B[x+1][y+1]=A[x][y]
    for x in range(H+1):
        for y in range(1,W+1):
            B[x][y] += B[x][y-1]
    for x in range(1,H+1):
        for y in range(W+1):
            B[x][y] += B[x-1][y]
    return B
def fac(n, m=0):
    # nの階乗 | m:mod(デフォなし)
    if(n<=0): return 0
    P = 1
    for i in range(1,n+1):
        P *= i
        if(m>0): P %= m
    return P
def nCmMOD(A,B,Mod):
    # a conb b を Mod で割った余り 1絡みの挙動に注意する。
    # 大量にほしいときは階乗逆元を使うやつを持ってくる。
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod
def comb_table(N):
    # nCkのテーブルを作る, nCk = C[n][k]
    C = [[0 for i in range(N+1)] for j in range(N+1)]
    C[0][0] = 1
    for n in range(1,N+1):
        for k in range(n+1):
            C[n][k] = C[n-1][k-1] + C[n-1][k]
    return C
def nHk(A,B,Mod):
    # 重複組合せ：1~nの中から重複を許してk個のものを選ぶ組合せ
    return nCmMOD(A-1+B,A-1,Mod)
def factorization(n):
    # 素因数分解、1に注意
    arr = []; temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1: arr.append([temp, 1])
    if arr==[]: arr.append([n, 1])
    return arr
def get_primes(n: int) -> list:
    # n以下の素数表
    sieve=[1]*n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i] = [0] * ((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]
#@lru_cache(maxsize=2*10**5)
def division(a, b, m):
    # a÷bをmod mで求める 大量に使うときはメモ化
    return (a * pow(b, m - 2, m)) % m
memod=defaultdict(lambda:-1)
def gcd(a,b):
    # 最大公約数
    while b!=0: a,b = b,a%b
    return a
def lcm(a,b):
    # 最小公倍数
    return(a*b // gcd(a,b))
def make_divisors(n):
    # nの約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    #divisors.sort()
    return(divisors)
def ran(A):
    # ランレングス圧縮
    L = list(A); T = []
    for i in range(len(L)):
        if i==0: T.append([L[0],1])
        else:
            if L[i]==L[i-1]: T[-1][1]+=1
            else: T.append([L[i],1])
    #return T
    ans1,ans2=[],[]
    for i in range(len(T)):
        ans1.append(T[i][0]) #種目
        ans2.append(T[i][1]) #個数
    return ans1,ans2
def dot(P,Q,a,b,c):
    # P(a,b), Q(b,c) の行列積, abcに1が入るときは注意
    ret = LL(a,c)
    for i in range(a):
        for j in range(c):
            for k in range(b):
                ret[i][j] += P[i][k] * Q[k][j]
    return ret
def Trans(arr,h,w):
    # 配列の転置
    ret=LL(w,h)
    for i in range(h):
        for j in range(w): ret[j][i] = arr[i][j]
    return ret

# Union-Find---------------------------------------
#Root=list(range(N))
#Size=[1]*N
def find_root(root,x):
    y = root[x]
    if x == y: return x
    z = find_root(root,y)
    root[x] = z
    return z
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y: return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
def getValue(root,size,x):
    return size[find_root(root,x)]
def same(root,x,y):
    return (find_root(root,x)==find_root(root,y))

# itertools
"""
array=[1,2,3]
PMT = permutations(array) #順列
#123,132,213,231,312,321
PMT2 = permutations(array,2)
#12,13,21,23,31,32
CMB1 = combinations(array,2) #組合せ
#12,13,23
CMB2 = combinations_with_replacement(array,2) #重複組合せ
#11,12,13,22,23,33
def all_comb(array):
    #全組合せ(個数1~N)
    ret=[]
    for i in range(len(array)+1):
        ret+=list(combinations(array,i))
    return ret
#-,1,2,3,12,13,23,123
array2=[0,1]
PRD1 = product(array2,repeat=3) #直積
#000,001,010,011,100,101,110,111
"""


"""
#A
A,B,C=MI()
ANS=set([])
for i in range(1,1000001):
    c=i*A
    if c-B>0:
        c-=B
    if c==C:
        ANS.add(i)
ANS=sorted(list(ANS))
for i in ANS:
    print(i)
if len(ANS)==0:
    print(-1)
"""



"""
#B
Q=II()
B=[0]*31
S=set([])
for q in range(Q):
    query=LI()
    if query[0]==1:
        a=query[1]
        if a not in S:
            al="{:b}".format(a).rjust(31,'0')
            for i in range(31):
                if al[i]=="1": B[i]+=1
            S.add(a)

    if query[0]==2:
        a=query[1]
        if a in S:
            S.discard(a)
            al="{:b}".format(a).rjust(31,'0')
            for i in range(31):
                if al[i]=="1": B[i]-=1
    
    if query[0]==3:
        ans=0
        b=B[::-1]
        k=len(S)
        if k==0:
            print(-1)
            continue
        for i in range(31):
            if b[i]==k:
                ans += 2**i
        print(ans)


"""

"""
#B
Q=II()
B=[0]*31
S=set([])
l=0
P=[2**i for i in range(32)]

for q in range(Q):
    query=LI()
    t=query[0]
    if t==1:
        a=query[1]
        if a not in S:
            S.add(a)
            l+=1
            for i in range(31):
                B[i] += a%2
                a //= 2
    
    if t==2:
        a=query[1]
        if a in S:
            S.discard(a)
            l-=1
            for i in range(31):
                B[i] -= a%2
                a //= 2
    
    if t==3:
        ans=0
        if l==0:
            print(-1)
            continue
        for i in range(31):
            if B[i]==l:
                ans += P[i]
        print(ans)
    
    #print(B)

"""

"""
#C
N=II()
A=LI()
B=LI()
X=LI()
Y=LI()

# dp[x][y] := x番目まで見て、x番目が色yである場合の最大得点

dp=LL(2*N+10, 2)

for i in range(2*N):
    if i==0:
        dp[0][0] = A[0]
        dp[0][1] = B[0]
    elif i%2==0:
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + A[i]
        dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + B[i]
    else:
        dp[i][0] = max(dp[i-1][0]+X[i//2], dp[i-1][1]+Y[i//2]) + A[i]
        dp[i][1] = max(dp[i-1][1]+X[i//2], dp[i-1][0]+Y[i//2]) + B[i]

print(max(dp[2*N-1]))
#print(dp)
"""


#D
N,K=MI()
TL=[0]*110000
ANS=1

# xと滞在時間がかぶるとは、
# 開始時間がlxより早く、終了時間がlxより後 または
# 開始時間がlxより遅く、rxより前
# ソートしておけば前者だけ見れば良くなる。
# 補修合を考えてうまくいく問題の可能性もあり

C=[]
for i in range(N):
    l,r=MI()
    C.append((l,r))
C.sort()

R=[]
k=0
for (l,r) in C:
    num = k - bisect_right(R, l)
    #print(R, l, num)
    insort(R,r)
    k+=1
    ANS *= max(0, K-num)
    ANS %= mod

#print(ANS)
ANS = (pow(K, N, mod)  + mod - ANS) % mod
print(ANS)

yukicoder

結果

テストケース

ソースコード