結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー | CHOHCOOH2 |
提出日時 | 2019-07-16 10:05:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,766 ms / 5,000 ms |
コード長 | 2,068 bytes |
コンパイル時間 | 305 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 92,756 KB |
最終ジャッジ日時 | 2024-05-07 10:32:05 |
合計ジャッジ時間 | 14,622 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
52,352 KB |
testcase_01 | AC | 37 ms
52,352 KB |
testcase_02 | AC | 38 ms
53,120 KB |
testcase_03 | AC | 37 ms
52,352 KB |
testcase_04 | AC | 38 ms
52,608 KB |
testcase_05 | AC | 170 ms
77,312 KB |
testcase_06 | AC | 240 ms
77,848 KB |
testcase_07 | AC | 167 ms
76,340 KB |
testcase_08 | AC | 344 ms
79,400 KB |
testcase_09 | AC | 959 ms
85,220 KB |
testcase_10 | AC | 1,367 ms
86,300 KB |
testcase_11 | AC | 515 ms
79,936 KB |
testcase_12 | AC | 984 ms
84,392 KB |
testcase_13 | AC | 311 ms
78,544 KB |
testcase_14 | AC | 536 ms
86,444 KB |
testcase_15 | AC | 1,541 ms
92,756 KB |
testcase_16 | AC | 1,473 ms
90,116 KB |
testcase_17 | AC | 1,766 ms
90,268 KB |
testcase_18 | AC | 1,055 ms
88,692 KB |
testcase_19 | AC | 1,157 ms
89,100 KB |
ソースコード
import sys input=sys.stdin.readline N=int(input()) n=1 while(n<N): n*=2 INF=0 dat=[INF]*(2*n-1) lazy=[-1]*(2*n-1) def find(a,b,k,l,r): if r<=a or b<=l: return INF eval(k,l,r) if a<=l and r<=b: return dat[k] else: vl=find(a,b,k*2+1,l,(l+r)//2) vr=find(a,b,k*2+2,(l+r)//2,r) return vl+vr def eval(k,l,r): if lazy[k]!=-1:#遅延配列が0かどうか dat[k]=lazy[k] if r-l>1:#最下段かのチェック lazy[2*k+1]=lazy[k]//2 lazy[2*k+2]=lazy[k]//2 lazy[k]=-1#伝搬終了 def add(a,b,x,k,l,r): eval(k,l,r) if b<=l or r<=a: return if a<=l and r<=b: lazy[k]=(r-l)*x eval(k,l,r) else: add(a,b,x,2*k+1,l,(l+r)//2) add(a,b,x,2*k+2,(l+r)//2,r) dat[k]=dat[2*k+1]+dat[2*k+2] dat1=[INF]*(2*n-1) lazy1=[0]*(2*n-1) def find1(a,b,k,l,r): if r<=a or b<=l: return INF eval1(k,l,r) if a<=l and r<=b: return dat1[k] else: vl=find1(a,b,k*2+1,l,(l+r)//2) vr=find1(a,b,k*2+2,(l+r)//2,r) return vl+vr def eval1(k,l,r): if lazy1[k]!=-1:#遅延配列が0かどうか dat1[k]=lazy1[k] if r-l>1:#最下段かのチェック lazy1[2*k+1]=lazy1[k]//2 lazy1[2*k+2]=lazy1[k]//2 lazy1[k]=-1#伝搬終了 def add1(a,b,x,k,l,r): eval1(k,l,r) if b<=l or r<=a: return if a<=l and r<=b: lazy1[k]=(r-l)*x eval1(k,l,r) else: add1(a,b,x,2*k+1,l,(l+r)//2) add1(a,b,x,2*k+2,(l+r)//2,r) dat1[k]=dat1[2*k+1]+dat1[2*k+2] ap=0 bp=0 Q=int(input()) for i in range(Q): x,l,r=map(int,input().split()) if x==0: f=find1(l,r+1,0,0,n) a=find(l,r+1,0,0,n) b=f-a if a>b: ap+=a elif b>a: bp+=b elif x==1: add(l,r+1,1,0,0,n) add1(l,r+1,1,0,0,n) elif x==2: add(l,r+1,0,0,0,n) add1(l,r+1,1,0,0,n) f=find1(0,N,0,0,n) a=find(0,N,0,0,n) b=f-a ap+=a bp+=b print(ap,bp)