結果
| 問題 | No.2875 What is My Rank? |
| ユーザー |
 kainade
|
| 提出日時 | 2024-09-11 21:53:36 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 352 ms / 2,000 ms |
| コード長 | 22,919 bytes |
| コンパイル時間 | 353 ms |
| コンパイル使用メモリ | 82,156 KB |
| 実行使用メモリ | 100,320 KB |
| 最終ジャッジ日時 | 2024-09-11 21:53:46 |
| 合計ジャッジ時間 | 10,317 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 66 ms
73,868 KB |
| testcase_01 | AC | 67 ms
73,448 KB |
| testcase_02 | AC | 66 ms
72,740 KB |
| testcase_03 | AC | 67 ms
73,004 KB |
| testcase_04 | AC | 67 ms
73,008 KB |
| testcase_05 | AC | 66 ms
74,200 KB |
| testcase_06 | AC | 69 ms
73,164 KB |
| testcase_07 | AC | 67 ms
74,004 KB |
| testcase_08 | AC | 87 ms
73,332 KB |
| testcase_09 | AC | 349 ms
100,320 KB |
| testcase_10 | AC | 339 ms
100,016 KB |
| testcase_11 | AC | 350 ms
99,604 KB |
| testcase_12 | AC | 200 ms
86,604 KB |
| testcase_13 | AC | 202 ms
87,700 KB |
| testcase_14 | AC | 136 ms
82,120 KB |
| testcase_15 | AC | 310 ms
98,036 KB |
| testcase_16 | AC | 277 ms
94,612 KB |
| testcase_17 | AC | 209 ms
88,668 KB |
| testcase_18 | AC | 332 ms
96,364 KB |
| testcase_19 | AC | 293 ms
94,644 KB |
| testcase_20 | AC | 157 ms
83,552 KB |
| testcase_21 | AC | 168 ms
84,392 KB |
| testcase_22 | AC | 215 ms
88,192 KB |
| testcase_23 | AC | 296 ms
96,064 KB |
| testcase_24 | AC | 352 ms
98,908 KB |
| testcase_25 | AC | 215 ms
87,600 KB |
| testcase_26 | AC | 145 ms
82,232 KB |
| testcase_27 | AC | 199 ms
86,560 KB |
| testcase_28 | AC | 187 ms
85,992 KB |
| testcase_29 | AC | 215 ms
88,072 KB |
| testcase_30 | AC | 224 ms
88,676 KB |
| testcase_31 | AC | 128 ms
80,676 KB |
| testcase_32 | AC | 274 ms
93,204 KB |
| testcase_33 | AC | 193 ms
97,788 KB |
| testcase_34 | AC | 298 ms
99,504 KB |
ソースコード
def main():
N=II()
LR=LL(N)
ans=0
l0,r0=LR[0]
for i in range(1,N):
l,r=LR[i]
denomi=0
#x=[l0,l)かつ[l0,r0+1)の時 r-l+1
denomi+=(r-l+1)*max(0,min(l,r0+1)-l0)
#x=[l,r)かつ[l0,r0+1)の時 r-x
lo=max(l,l0)
hi=min(r-1,r0)
if lo<=hi:
lo,hi=r-hi,r-lo
denomi+=(lo+hi)*(hi-lo+1)//2
ans+=denomi%MOD*pow(r-l+1,-1,MOD)%MOD
ans=ans*pow(r0-l0+1,-1,MOD)+1
print(ans%MOD)
# user config
############
DEBUG_MODE=1
############
# import
import sys
import itertools
import bisect
import math
from collections import *
from functools import cache
from heapq import *
# alias
DD = defaultdict
BSL = bisect.bisect_left
BSR = bisect.bisect_right
# config
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
# input
def II(): return int(input())
def IS(): return input()[:-1]
def MI(): return map(int,input().split())
def LM(): return list(MI())
def LL(n): return [LM() for _ in range(n)]
def MI_1(): return map(lambda x:int(x)-1,input().split())
def LM_1(): return list(MI_1())
def LL_1(n): return [LM_1() for _ in range(n)]
def ALPHABET_TO_NUM(string, upper=False): return list(map(lambda elm:ord(elm)-ord("A") if upper else ord(elm)-ord("a"), string))
# functions
def DB(*args,**kwargs):
global DEBUG_MODE
if not DEBUG_MODE:
return
if args:
print(*args)
return
for name, value in kwargs.items():
print(f"{name} : {value}")
def bit_count(num):
length = num.bit_length()
res = 0
for i in range(length):
if num >> i & 1:
res += 1
return res
def popcount64(n):
# 63桁まで高速に動く.64桁まで正常に動く.
c=(n&0x5555555555555555)+((n>>1)&0x5555555555555555)
c=(c&0x3333333333333333)+((c>>2)&0x3333333333333333)
c=(c&0x0f0f0f0f0f0f0f0f)+((c>>4)&0x0f0f0f0f0f0f0f0f)
c=(c&0x00ff00ff00ff00ff)+((c>>8)&0x00ff00ff00ff00ff)
c=(c&0x0000ffff0000ffff)+((c>>16)&0x0000ffff0000ffff)
c=(c&0x00000000ffffffff)+((c>>32)&0x00000000ffffffff)
return c
def argmax(*args):
if len(args) == 1 and hasattr(args[0], '__iter__'):
lst = args[0]
else:
lst = args
return lst.index(max(lst))
def argmin(*args):
if len(args) == 1 and hasattr(args[0], '__iter__'):
lst = args[0]
else:
lst = args
return lst.index(min(lst))
def prefix_op(lst, op=lambda x,y:x+y, e=0):
N = len(lst)
res = [e]*(N+1)
for i in range(N):
res[i+1] = op(res[i], lst[i])
return res
def suffix_op(lst, op=lambda x,y:x+y, e=0):
N = len(lst)
res = [e]*(N+1)
for i in range(N):
res[N-1-i] = op(lst[N-1-i], res[N-i])
return res
def sigma_LinearFunc(coeff1, coeff0, left, right, MOD=None):
"""
coeff1*x + coeff0
の x = [left, right] の和を求める.
MODで計算したい場合、区間の引数をMOD取った上で代入しても良い.
そのとき、left > right となってもよい.
"""
if MOD:
# MODが素数でない場合にも対応するように、和公式を適応後に剰余を計算.
return ((coeff0%MOD*((right-left+1)%MOD)%MOD) + (coeff1%MOD*((left+right)*(right-left+1)//2%MOD)%MOD))%MOD
return coeff0*(right-left+1) + coeff1*(left+right)*(right-left+1)//2
def find_divisors(n):
divs_small, divs_big = [], []
i = 1
while i * i <= n:
if n % i == 0:
divs_small.append(i)
divs_big.append(n // i)
i += 1
if divs_big[-1] == divs_small[-1]:
divs_big.pop()
for e in reversed(divs_big):
divs_small.append(e)
return divs_small
def prime_factorization(n):
n_intact = n
ret = []
i = 2
while i * i <= n_intact:
if n % i == 0:
cnt = 0
while n % i == 0:
n //= i
cnt += 1
ret.append((i,cnt))
i += 1
if n != 1: ret.append((n,1))
return ret
""" 矩形の二次元配列を扱う諸関数 """
def copy_table(table):
H,W = len(table), len(table[0])
res = []
for i in range(H):
res.append([])
for j in range(W):
res[-1].append(table[i][j])
return res
def sum_table(table, MOD=None):
H,W = len(table), len(table[0])
res = 0
for i in range(H):
for j in range(W):
res += table[i][j]
if MOD:
res %= MOD
return res
def transpose_table(table):
H,W = len(table), len(table[0])
res = [[None]*H for _ in range(W)]
for i in range(H):
for j in range(W):
res[j][i] = table[i][j]
return res
def convert_table_to_bit(table, letter1="#", rev=False):
H,W = len(table), len(table[0])
res = []
for h in range(H):
rowBit = 0
for w in range(W):
if rev:
if table[h][w] == letter1:
rowBit += 2**w
else:
if table[h][W-w-1] == letter1:
rowBit += 2**w
res.append(rowBit)
return res
def rotate_table_cc(S): return list(zip(*S))[::-1]
def rotate_table_c(S): return list(zip(*S[::-1]))
def mul_matrix(A, B, mod):
N = len(A)
K = len(A[0])
M = len(B[0])
res = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N) :
for j in range(K) :
for k in range(M) :
res[i][k] += A[i][j] * B[j][k]
res[i][k] %= mod
return res
def pow_matrix(mat, exp, mod):
N = len(mat)
res = [[1 if i == j else 0 for i in range(N)] for j in range(N)]
while exp > 0 :
if exp%2 == 1 :
res = mul_matrix(res, mat, mod)
mat = mul_matrix(mat, mat, mod)
exp //= 2
return res
def compress(lst):
D = {e:i for i,e in enumerate(sorted(set(lst)))}
return [D[e] for e in lst]
def highDimCompress(lst):
#(x,y)の配列や,(x,y,z)の配列が与えられたとき,軸ごとに座圧する.
return list(zip(*list(map(compress,list(zip(*lst))))))
#classes
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional
T = TypeVar('T')
class SortedSet(Generic[T]):
BUCKET_RATIO = 16
SPLIT_RATIO = 24
def __init__(self, a: Iterable[T] = []) -> None:
"Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"
a = list(a)
n = self.size = len(a)
if any(a[i] > a[i + 1] for i in range(n - 1)):
a.sort()
if any(a[i] >= a[i + 1] for i in range(n - 1)):
a, b = [], a
for x in b:
if not a or a[-1] != x:
a.append(x)
bucket_size = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
self.a = [a[n * i // bucket_size : n * (i + 1) // bucket_size] for i in range(bucket_size)]
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i: yield j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i): yield j
def __eq__(self, other) -> bool:
return list(self) == list(other)
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedSet" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _position(self, x: T) -> Tuple[List[T], int, int]:
"return the bucket, index of the bucket and position in which x should be. self must not be empty."
for i, a in enumerate(self.a):
if x <= a[-1]: break
return (a, i, bisect_left(a, x))
def __contains__(self, x: T) -> bool:
if self.size == 0: return False
a, _, i = self._position(x)
return i != len(a) and a[i] == x
def add(self, x: T) -> bool:
"Add an element and return True if added. / O(√N)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return True
a, b, i = self._position(x)
if i != len(a) and a[i] == x: return False
a.insert(i, x)
self.size += 1
if len(a) > len(self.a) * self.SPLIT_RATIO:
mid = len(a) >> 1
self.a[b:b+1] = [a[:mid], a[mid:]]
return True
def _pop(self, a: List[T], b: int, i: int) -> T:
ans = a.pop(i)
self.size -= 1
if not a: del self.a[b]
return ans
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0: return False
a, b, i = self._position(x)
if i == len(a) or a[i] != x: return False
self._pop(a, b, i)
return True
def lt(self, x: T) -> Optional[T]:
"Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] < x:
return a[bisect_left(a, x) - 1]
def le(self, x: T) -> Optional[T]:
"Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] <= x:
return a[bisect_right(a, x) - 1]
def gt(self, x: T) -> Optional[T]:
"Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
if a[-1] > x:
return a[bisect_right(a, x)]
def ge(self, x: T) -> Optional[T]:
"Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
if a[-1] >= x:
return a[bisect_left(a, x)]
def __getitem__(self, i: int) -> T:
"Return the i-th element."
if i < 0:
for a in reversed(self.a):
i += len(a)
if i >= 0: return a[i]
else:
for a in self.a:
if i < len(a): return a[i]
i -= len(a)
raise IndexError
def pop(self, i: int = -1) -> T:
"Pop and return the i-th element."
if i < 0:
for b, a in enumerate(reversed(self.a)):
i += len(a)
if i >= 0: return self._pop(a, ~b, i)
else:
for b, a in enumerate(self.a):
if i < len(a): return self._pop(a, b, i)
i -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
"""
(num, cnt)を要素としたSSを管理してMultiset化したいとき用.
"""
def exist(self, x):
ret = self.gt((x,0))
if ret is None:
return False
elif ret[0] == x:
return True
else:
return False
def increment(self, x):
if not self.exist(x):
self.add((x,1))
else:
num, cnt = self.gt((x,0))
self.discard((x,cnt))
self.add((x,cnt+1))
def decrement(self, x):
if not self.exist(x):
return
num, cnt = self.gt((x,0))
if cnt == 1:
self.discard((x,cnt))
else:
self.discard((x,cnt))
self.add((x,cnt-1))
def multi_add(self, x, y):
if not self.exist(x):
self.add((x,y))
else:
num, cnt = self.gt((x,0))
self.discard((x,cnt))
self.add((x,cnt+y))
def multi_sub(self, x, y):
if not self.exist(x):
return
num, cnt = self.gt((x,0))
if cnt <= y:
self.discard((x,cnt))
else:
self.discard((x,cnt))
self.add((x,cnt-y))
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
T = TypeVar('T')
class SortedMultiset(Generic[T]):
BUCKET_RATIO = 16
SPLIT_RATIO = 24
def __init__(self, a: Iterable[T] = []) -> None:
"Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
a = list(a)
n = self.size = len(a)
if any(a[i] > a[i + 1] for i in range(n - 1)):
a.sort()
num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i: yield j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i): yield j
def __eq__(self, other) -> bool:
return list(self) == list(other)
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedMultiset" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _position(self, x: T) -> Tuple[List[T], int, int]:
"return the bucket, index of the bucket and position in which x should be. self must not be empty."
for i, a in enumerate(self.a):
if x <= a[-1]: break
return (a, i, bisect_left(a, x))
def __contains__(self, x: T) -> bool:
if self.size == 0: return False
a, _, i = self._position(x)
return i != len(a) and a[i] == x
def count(self, x: T) -> int:
"Count the number of x."
return self.index_right(x) - self.index(x)
def add(self, x: T) -> None:
"Add an element. / O(√N)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return
a, b, i = self._position(x)
a.insert(i, x)
self.size += 1
if len(a) > len(self.a) * self.SPLIT_RATIO:
mid = len(a) >> 1
self.a[b:b+1] = [a[:mid], a[mid:]]
def _pop(self, a: List[T], b: int, i: int) -> T:
ans = a.pop(i)
self.size -= 1
if not a: del self.a[b]
return ans
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0: return False
a, b, i = self._position(x)
if i == len(a) or a[i] != x: return False
self._pop(a, b, i)
return True
def lt(self, x: T) -> Optional[T]:
"Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] < x:
return a[bisect_left(a, x) - 1]
def le(self, x: T) -> Optional[T]:
"Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] <= x:
return a[bisect_right(a, x) - 1]
def gt(self, x: T) -> Optional[T]:
"Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
if a[-1] > x:
return a[bisect_right(a, x)]
def ge(self, x: T) -> Optional[T]:
"Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
if a[-1] >= x:
return a[bisect_left(a, x)]
def __getitem__(self, i: int) -> T:
"Return the i-th element."
if i < 0:
for a in reversed(self.a):
i += len(a)
if i >= 0: return a[i]
else:
for a in self.a:
if i < len(a): return a[i]
i -= len(a)
raise IndexError
def pop(self, i: int = -1) -> T:
"Pop and return the i-th element."
if i < 0:
for b, a in enumerate(reversed(self.a)):
i += len(a)
if i >= 0: return self._pop(a, ~b, i)
else:
for b, a in enumerate(self.a):
if i < len(a): return self._pop(a, b, i)
i -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
class Comb:
def __init__(self,table_len,mod):
"""
modが素数の場合しか使用できない.
table_len に指定した数まで法modでのコンビネーションの計算が可能になる.
"""
self.fac = [1,1]
self.inv = [1,1]
self.finv = [1,1]
self.mod = mod
for i in range(2,table_len+1):
self.fac.append(self.fac[i-1]*i%mod)
self.inv.append(-self.inv[mod%i]*(mod//i)%mod)
self.finv.append(self.finv[i-1]*self.inv[i]%mod)
def comb(self,a,b):
return self.fac[a]*self.finv[b]*self.finv[a-b]%self.mod
class GridBFS:
def __init__(self, table):
#二次元配列や文字列の配列を受け取る.
self.table = table
self.H = len(table)
self.W = len(table[0])
self.wall = "#"
def find(self, c):
#table から引数の文字を探しインデックスを返す. 無い時、None.
for h in range(self.H):
for w in range(self.W):
if self.table[h][w] == c:
return (h,w)
return None
def set_wall_string(self, string):
#壁として扱う文字を "#!^" の様に文字列リテラルで格納. 初期値は、"#"
self.wall = string
def island(self, transition = [[-1,0],[0,1],[1,0],[0,-1]]):
H, W = self.H, self.W
self.island_id = [[-1]*W for _ in range(H)]
self.island_size = [[-1]*W for _ in range(W)]
crr_id = 0
id2size = dict()
for sh in range(H):
for sw in range(W):
if self.table[sh][sw] in self.wall:
continue
if self.island_id[sh][sw] != -1:
continue
deq = deque()
deq.append((sh,sw))
crr_size = 1
self.island_id[sh][sw] = crr_id
while deq:
h,w = deq.popleft()
for dh, dw in transition:
nh, nw = h+dh, w+dw
if (not 0<=nh<H) or (not 0<=nw<W):
continue
if self.table[nh][nw] in self.wall:
continue
if self.island_id[nh][nw] == -1:
self.island_id[nh][nw] = crr_id
deq.append((nh, nw))
crr_size += 1
id2size[crr_id] = crr_size
crr_id += 1
for h in range(H):
for w in range(W):
if self.table[h][w] in self.wall:
continue
self.island_size[h][w] = id2size[self.island_id[h][w]]
return self.island_id, self.island_size
def distance(self, start, goal=None, transition = [[-1,0],[0,1],[1,0],[0,-1]]):
#goal指定したら、goalまでの最短距離を、指定しなければdist配列を返す. 到達不可能は -1.
#二次元配列上での遷移方法を transition で指定できる. 初期値は上下左右.
H, W, tab, wall = self.H, self.W, self.table, self.wall
INF = 1<<60
deq = deque()
deq.append(start)
dist = [[INF]*W for _ in range(H)]
dist[start[0]][start[1]] = 0
if start == goal:
return 0
while deq:
h,w = deq.popleft()
for dh, dw in transition:
nh = h+dh
nw = w+dw
# gridの範囲外.
if (not 0<=nh<H) or (not 0<=nw<W):
continue
# wallに設定されている文字なら.
if tab[nh][nw] in wall:
continue
new_dist = dist[h][w] + 1
#goalが引数で与えられていてgoalに達したら終了.
if goal and (nh,nw)==goal:
return new_dist
if dist[nh][nw] > new_dist:
dist[nh][nw] = new_dist
deq.append((nh,nw))
# goalが設定されていていまだreturnされていないなら,
# goalに到達できなかったということ.
if goal:
return -1
return dist
class nth_root:
def __init__(self):
self.ngs = [-1, -1, 4294967296, 2642246, 65536, 7132, 1626, 566, 256, 139, 85, 57, 41, 31, 24, 20, 16, 14, 12, 11, 10, 9, 8, 7, 7, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
""" pre-calculated by this code """
# self.ngs = [-1,-1]
# for n in range(2,64):
# ok,ng=2**33,0
# while abs(ok-ng)>1:
# mid=ok+ng>>1
# if mid**n>=2**64:
# ok=mid
# else:
# ng=mid
# self.ngs.append(ok)
""" xが64bitに収まる時高速. そうでないときも動作するが速度の保証無し. """
def calc(self, x, n, is_x_within_64bit=True):
if x<=1 or n==1: return x
if is_x_within_64bit:
if n>=64: return 1
ng = self.ngs[n]
else:
ng = x
ok = 0
while abs(ok-ng)>1:
mid = ok+ng>>1
if mid**n <= x:
ok = mid
else:
ng = mid
return ok
# well-used const
global DIRECTION_4, DIRECTION_8, DIRECTION_DIAGONAL, DIRECTION_URDL_TABLE, DIRECTION_URDL_COORD_PLANE, MOD, INF, LOWER_ALP, UPPER_ALP, ALL_ALP
# clockwise from top.
DIRECTION_4 = [[-1,0],[0,1],[1,0],[0,-1]]
DIRECTION_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
DIRECTION_DIAGONAL = [[-1,1],[1,1],[1,-1],[-1,-1]]
DIRECTION_URDL_TABLE = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}
DIRECTION_URDL_COORD_PLANE = {'U':(0,1), 'R':(1,0), 'D':(0,-1), 'L':(-1,0)}
MOD = 998244353
INF = 1<<60
LOWER_ALP = "abcdefghijklmnopqrstuvwxyz"
UPPER_ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ALL_ALP = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
main()