結果
問題 | No.151 セグメントフィッシング |
ユーザー |
|
提出日時 | 2024-03-21 02:03:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 132 ms / 5,000 ms |
コード長 | 2,749 bytes |
コンパイル時間 | 254 ms |
コンパイル使用メモリ | 82,236 KB |
実行使用メモリ | 78,072 KB |
最終ジャッジ日時 | 2024-09-30 09:57:38 |
合計ジャッジ時間 | 3,953 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 19 |
ソースコード
import sysimport mathimport bisectfrom heapq import heapify, heappop, heappushfrom collections import deque, defaultdict, Counterfrom functools import lru_cachefrom itertools import accumulate, combinations, permutations, productsys.setrecursionlimit(1000000)MOD = 10 ** 9 + 7MOD99 = 998244353input = lambda: sys.stdin.readline().strip()NI = lambda: int(input())NMI = lambda: map(int, input().split())NLI = lambda: list(NMI())SI = lambda: input()SMI = lambda: input().split()SLI = lambda: list(SMI())EI = lambda m: [NLI() for _ in range(m)]class BIT():"""BIT 0-index ACL for pythonadd(p, x): p番目にxを加算get(p): p番目を取得sum0(r): [0:r)の和を取得sum(l, r): [l:r)の和を取得"""def __init__(self, N):self.n = Nself.data = [0 for i in range(N)]def add(self, p, x):assert 0 <= p < self.n, "0<=p<n,p={0},n={1}".format(p, self.n)p += 1while (p <= self.n):self.data[p - 1] += xp += p & -pdef get(self, p):return self.sum(p, p + 1)def sum(self, l, r):assert (0 <= l and l <= r and r <= self.n), "0<=l<=r<=n,l={0},r={1},n={2}".format(l, r, self.n)return self.sum0(r) - self.sum0(l)def sum0(self, r):s = 0while (r > 0):s += self.data[r - 1]r -= r & -rreturn sdef debug(self):res = [self.get(p) for p in range(self.n)]return resdef main():N, Q = NMI()# N-1, N-2, ..., 1, 0, 0, 1, ..., N-1# 魚はこの中を全部右に動き、端で消えて左から出てくるとする# Rの魚は右側、Lの魚は左側に入るが、そこからt巻き戻した位置に入れる# Cは2箇所作ったうえでtずらすbit = BIT(2*N)for t in range(Q):x, y, z = SMI()y, z = int(y), int(z)if x == "L":p = (N-1-y-t) % (2*N)bit.add(p, z)elif x == "R":p = (y+N-t) % (2*N)bit.add(p, z)else:ans = 0ry, rz = N+y-t, N+z-tly, lz = N-z-t, N-y-t# print(t, ly, lz, ry, rz)if ry // (2*N) == rz // (2*N):ans += bit.sum(ry % (2*N), rz % (2*N))else:ans += bit.sum(0, rz % (2 * N))ans += bit.sum(ry % (2 * N), 2*N)if ly // (2*N) == lz // (2*N):ans += bit.sum(ly % (2*N), lz % (2*N))else:ans += bit.sum(0, lz % (2 * N))ans += bit.sum(ly % (2 * N), 2*N)print(ans)# print(x, y, z, bit.debug())if __name__ == "__main__":main()