結果
問題 |
No.255 Splarrraaay スプラーレェーーイ
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:19:40 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 4,716 bytes |
コンパイル時間 | 239 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 274,476 KB |
最終ジャッジ日時 | 2025-03-20 20:20:42 |
合計ジャッジ時間 | 16,251 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 MLE * 1 -- * 6 |
ソースコード
import bisect MOD = 10**18 + 9 def main(): import sys input = sys.stdin.read data = input().split() ptr = 0 N = int(data[ptr]) ptr += 1 Q = int(data[ptr]) ptr +=1 intervals = [(0, N-1, 0, 0)] global_sums = [0] * 5 # A, B, C, D, E bonus_points = [0] *5 for _ in range(Q): x = int(data[ptr]) l = int(data[ptr+1]) r = int(data[ptr+2]) ptr +=3 if x ==0: # Bonus query sums = [0]*5 for iv in intervals: s, e, owner, cnt = iv if owner ==0: continue os = max(s, l) oe = min(e, r) if os > oe: continue length = oe - os +1 team_idx = owner -1 if 0 <= team_idx <5: sums[team_idx] += cnt * length max_sum = max(sums) count = sums.count(max_sum) if count ==1 and max_sum >0: team_idx = sums.index(max_sum) bonus_points[team_idx] = (bonus_points[team_idx] + max_sum) % MOD else: team_idx = x-1 # x is 1-5, team_idx 0-4 new_intervals = [] to_process = [] for iv in intervals: s, e, owner, cnt = iv if e < l or s > r: new_intervals.append(iv) else: to_process.append(iv) for iv in to_process: s, e, owner, cnt = iv left_start = s left_end = min(e, l-1) mid_start = max(s, l) mid_end = min(e, r) right_start = max(s, r+1) right_end = e if left_start <= left_end: new_intervals.append( (left_start, left_end, owner, cnt) ) if right_start <= right_end: new_intervals.append( (right_start, right_end, owner, cnt) ) if mid_start > mid_end: continue mid_owner = owner mid_cnt = cnt if mid_owner == (team_idx +1): # team_idx is 0-4, so +1 is 1-5 new_cnt = mid_cnt +1 else: new_owner = team_idx +1 new_cnt = 1 mid_owner = new_owner mid_iv = (mid_start, mid_end, mid_owner, new_cnt) # Update global sums mid_len = mid_end - mid_start +1 if owner != mid_owner: if owner >=1: orig_team = owner -1 global_sums[orig_team] = (global_sums[orig_team] - cnt * mid_len) % MOD global_sums[team_idx] = (global_sums[team_idx] + new_cnt * mid_len) % MOD else: # same owner, new_cnt is cnt +1 global_sums[team_idx] = (global_sums[team_idx] + mid_len) % MOD # Insert mid_iv into new_intervals and merge pos = bisect.bisect_left(new_intervals, (mid_iv[0],)) new_intervals.insert(pos, mid_iv) # Check left while pos >0: left = new_intervals[pos-1] if left[1] >= mid_iv[0] -1 and left[2] == mid_iv[2] and left[3] == mid_iv[3]: merged = (left[0], mid_iv[1], left[2], left[3]) new_intervals.pop(pos-1) new_intervals.pop(pos-1) new_intervals.insert(pos-1, merged) pos -=1 mid_iv = merged else: break # Check right while pos < len(new_intervals)-1: right = new_intervals[pos+1] if mid_iv[1] >= right[0] -1 and right[2] == mid_iv[2] and right[3] == mid_iv[3]: merged = (mid_iv[0], right[1], mid_iv[2], mid_iv[3]) new_intervals.pop(pos) new_intervals.pop(pos) new_intervals.insert(pos, merged) mid_iv = merged else: break intervals.clear() intervals.extend(sorted(new_intervals, key=lambda x: x[0])) # Calculate final scores final = [ (global_sums[i] + bonus_points[i]) % MOD for i in range(5)] print(' '.join(map(str, final))) if __name__ == "__main__": main()