結果
| 問題 | No.2333 Slime Structure |
| ユーザー |
 navel_tos
|
| 提出日時 | 2023-05-31 01:03:14 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,389 ms / 3,000 ms |
| コード長 | 6,980 bytes |
| コンパイル時間 | 833 ms |
| コンパイル使用メモリ | 86,964 KB |
| 実行使用メモリ | 295,540 KB |
| 最終ジャッジ日時 | 2023-08-28 01:21:09 |
| 合計ジャッジ時間 | 60,731 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 77 ms
71,292 KB |
| testcase_01 | AC | 76 ms
71,308 KB |
| testcase_02 | AC | 1,412 ms
193,676 KB |
| testcase_03 | AC | 1,607 ms
224,120 KB |
| testcase_04 | AC | 1,866 ms
236,636 KB |
| testcase_05 | AC | 1,543 ms
208,544 KB |
| testcase_06 | AC | 1,862 ms
252,656 KB |
| testcase_07 | AC | 2,389 ms
279,252 KB |
| testcase_08 | AC | 2,325 ms
276,652 KB |
| testcase_09 | AC | 2,245 ms
276,792 KB |
| testcase_10 | AC | 2,241 ms
275,652 KB |
| testcase_11 | AC | 2,217 ms
276,008 KB |
| testcase_12 | AC | 1,508 ms
277,816 KB |
| testcase_13 | AC | 1,342 ms
266,968 KB |
| testcase_14 | AC | 1,309 ms
266,316 KB |
| testcase_15 | AC | 1,383 ms
273,864 KB |
| testcase_16 | AC | 1,461 ms
279,484 KB |
| testcase_17 | AC | 1,611 ms
294,632 KB |
| testcase_18 | AC | 1,577 ms
291,820 KB |
| testcase_19 | AC | 1,604 ms
295,280 KB |
| testcase_20 | AC | 1,563 ms
294,216 KB |
| testcase_21 | AC | 1,640 ms
295,540 KB |
| testcase_22 | AC | 2,049 ms
273,528 KB |
| testcase_23 | AC | 2,128 ms
273,256 KB |
| testcase_24 | AC | 2,065 ms
273,268 KB |
| testcase_25 | AC | 1,934 ms
273,340 KB |
| testcase_26 | AC | 2,043 ms
273,260 KB |
| testcase_27 | AC | 2,053 ms
273,920 KB |
| testcase_28 | AC | 2,096 ms
273,080 KB |
| testcase_29 | AC | 2,046 ms
273,324 KB |
| testcase_30 | AC | 2,060 ms
272,900 KB |
| testcase_31 | AC | 2,088 ms
273,424 KB |
| testcase_32 | AC | 1,396 ms
274,016 KB |
ソースコード
#MMA Contest 015 L Slime Structure
'''
残り2問。Kは難しそうなのでLから(?)
■ABC303D Shift vs. CapsLock
aとAだけで構成された文字列Sがある。a,Shift+a,CapsLockだけで、最短で文字列Sを完成させろ。
Reference: https://atcoder.jp/contests/abc303/tasks/abc303_d
┏━━━━━━━┓┏━━━━┓ これの想定解はDPで、DP[i][j]: i文字目をCaps状態jで入力する
┃Shift ┃┃Caps ┃ 最短の時間 としてDPを回せばよいのだが、どうやらこの問題は
┃ ┏━━━┓ ┃┃Lock ┃ SegTreeに乗せることで、区間クエリ[L,R]あたりO(logN)で回答
┃ ┃ a ┃ ┃┃ ┃ することができるらしい。
┃ ┗━━━┛ ┃┃ ┃ 本問も同様の手法で解けるのではないだろうか。
┗━━━━━━━┛┗━━━━┛
Reference: https://twitter.com/simasimasukiyo/status/1662630417193930754?s=20
■考察
区間分割しないときつそうではある。
区間全幅を使うか、区間の左端だけを使うか、区間の右端だけを使うか、
みたいな感じでのり付けしていくのがベターかな。
区間を√Nで分割するとして、1回あたりの計算量はO(√N)くらいで収まりそう 多分
問題はクエリ1、一生更新するな
O(√N)で更新可能、それはそう。
連長圧縮されたスライムを、クエリ1で変更されるスライムで切断しておけばいいか。
とりあえずO(Q√N)には収まる、が、制約がN<10^5でありスライム切断クエリで実質的に
Nが増加することを考えるとかなり怪しい。
できればセグ木に乗せておきたい。
クエリ1で切断するぶんで区切っておき、セグ木には
1. 区間左端からの最大部分配列
2. 区間右端からの最大部分配列
3. 区間全域内での最大部分配列
4. 区間総和
を格納しておく必要がありそうだ。
そもそもこれ区間合成可能なの？
1. これらはたぶん大丈夫。採用区間左端/右端の最大部分配列を使うか、
2. それに隣の区間総和を足したものを比較すればよい。
違うな、区間全域と隣の左端、あるいは区間右端と隣の全域、のどちらかだ。
じゃあ区間全域を保持しないとだめか。
3. 区間またぎの有無で分ければいいか。
区間内最大か、区間右端と隣の左端の合成値のどちらかだろう。
4. わろす
ただ今回の制約だとどれも値が爆発するので、
Python的には残念だが、これらはすべてtuple型で保持しないとだめそうだ。
苦しい。
クエリ2を手動で解いてもいいが、それするくらいなら全てSegTreeに乗せてしまえ。
'''
#Segment Tree: O(logN)
class SegmentTree: # Segment Tree
def __init__(self,n,identity_e,combine_f): # 適応条件: 単位元eがある、互換可能
self._n=n; self._size=1 # モノイド(単位元)の例:
while self._size<self._n:self._size<<=1 # 足し算 0, かけ算 1, 最小 INF,
self._identity_e=identity_e # 最大 -INF, LCM(最小公倍数) 1
self._combine_f=combine_f #
self._node=[self._identity_e]*2*self._size # combine_f には関数を指定する
# def文で関数を自作してもいいし、
def build(self,array): # from operator import xor
assert len(array)==self._n,'array too large' # のようにimportしてもよい
for i,v in enumerate(array,start=self._size): #
self._node[i]=v # build: セグ木を建てる
for i in range(self._size-1,0,-1): # 異常時はassert関数でエラーを報告
self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
#
def update(self,index,value): # update: 一点更新 O(logN)
i=self._size+index; self._node[i]=value # 地点i(0-indexed)を更新する
while i-1: # 同時に上位のセグメントも更新する
i>>=1 #
self._node[i]=self._combine_f(self._node[i<<1|0],self._node[i<<1|1])
#
def fold(self,L,R): # fold: 区間取得 O(logN)
L+=self._size; R+=self._size # 区間 [L,R) の特定値を取得する
vL,vR=[self._identity_e]*2 #
while L<R: # nodeの遷移の考え方
if L&1: # ---1--- L: 自身より右の最小
vL=self._combine_f(vL,self._node[L]) # -2- -3- R: 自身-1より左の最小
L+=1 # 4 5 6 7 Rは計算より先に-1の
if R&1: # 処理をする点に注意
R-=1 # R---1---L
vR=self._combine_f(self._node[R],vR) # R-2- LLL. 例: L=6, R=5
L>>=1; R>>=1 # .R.5 L 7 Rの移動が変則的
return self._combine_f(vL,vR) # ←R L→
#SegTree用の関数を定義 node: (区間左端,右端,区間内 の最大スコア, 区間総長)を格納
f_n=lambda n,m:(max(n[0],n[3]+m[0]),max(m[1],n[1]+m[3]),max(n[2],m[2],n[1]+m[0]),n[3]+m[3])
import heapq as hq
f=lambda:list(map(int,input().split()))
#入力受取
N=int(input()); Slime=[f() for _ in range(N)]; Len=[]; total=0; INF=10**18
Q=int(input()); Tasks=[f() for _ in range(Q)]; Cut=[INF]
#スライムの分割箇所を決定
for t,L,R in Tasks:
if t==1: hq.heappush(Cut,L-1); hq.heappush(Cut,L)
if t==2: hq.heappush(Cut,L-1); hq.heappush(Cut,R)
#実際にスライムを分割
for attack,num in Slime:
while num and Cut[0]<=total+num:
if Cut[0]<=total: hq.heappop(Cut); continue
X=Cut[0]-total; Len.append((attack,X)); num-=X; total+=X; hq.heappop(Cut)
if num: Len.append((attack,num)); total+=num
#セグ木に乗せる準備 ノード作成と連想配列を用意
D=dict(); Unit=[(0,0,0,0)]; total=0; D[0]=0
for index,(attack,num) in enumerate(Len,start=1):
if attack>=0: Unit.append(tuple(attack*num for _ in range(4)))
else: Unit.append((attack,attack,attack,attack*num))
total+=num; D[total]=index
ST=SegmentTree(len(Unit),(-INF,-INF,-INF,0),f_n); ST.build(Unit)
#クエリを処理
for t,L,R in Tasks:
if t==1: ST.update(D[L],(R,R,R,R))
if t==2: print(ST.fold(D[L-1]+1,D[R]+1)[2])