結果

問題 No.3210 Fixed Sign Sequense
ユーザー dp_ijk
提出日時 2025-07-25 21:29:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 349 ms / 2,000 ms
コード長 2,797 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 144,648 KB
最終ジャッジ日時 2025-07-25 21:29:41
合計ジャッジ時間 9,664 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(N, S):
   pos = FenwickTree(N)
   neg = FenwickTree(N)
   for i, ch in enumerate(S):
      match ch:
         case "+":
            pos[i] = 1
         case "-":
            neg[i] = 1

   RLE = run_length(S)
   res = 0
   for k, (l, r) in RLE:
      if k == "+":
         res = max(res, r-l)
      if k == "-":
         res = max(res, r-l)

   for i, ch in enumerate(S):
      match ch:
         case "+":
            R = pos[i:]
            L = neg[:i]
            res = max(res, L+R)
         case "0":
            R = pos[i:]
            L = neg[:i]
            res = max(res, L+R+1)
   return res


class FenwickTree:
   def __init__(self, seq=()):
      if isinstance(seq, (int, float)):
         self.data = [0]*int(seq)
         self.N = len(self.data)
         self.tree = [0]*(self.N + 1)
         self.total = 0
      else:
         self.tree = [0]
         self.tree.extend(seq)
         self.data = [0+x for x in self.tree[1:]]
         self.total = sum(self.data)
         self.N = len(self.data)
         for i in range(1, self.N + 1):
            if i + (i& -i) <= self.N:
               self.tree[i + (i& -i)] += self.tree[i]

   def get(self, i):
      assert 0 <= i < self.N
      return self.data[i]

   def add(self, i, x):
      if x == 0: return
      assert 0 <= i < self.N
      self.data[i] += x
      self.total += x
      i += 1
      while i <= self.N:
         self.tree[i] += x
         i += i& -i

   def prefix(self, n):
      if n >= self.N: return self.total
      res = 0
      while n > 0:
         res += self.tree[n]
         n &= n-1
      return res

   def sum(self, l, r):
      if l < 0: l = 0
      if r > self.N: r = self.N
      if l >= r: return 0
      return self.prefix(r) - self.prefix(l)

   def __getitem__(self, idx: int|slice):
      if isinstance(idx, int):
         if idx < 0:
            idx += self.N
         return self.get(idx)
      else:
         l = idx.start
         r = idx.stop
         if l is None: l = 0
         if r is None: r = self.N
         return self.sum(l, r)

   def set(self, i, x):
      if i < 0:
         i += self.N
      self.add(i, x - self.get(i))

   __setitem__ = set

   def __delitem__(self, i):
      assert 0 <= i < self.N
      self.add(i, -self.get(i))

   def __iter__(self):
      return iter(self.data)

   def __repr__(self):
      return repr(self.data)

   def __len__(self):
      return self.N

   apply_at = add
   fold = sum


def run_length(A, *, key=None):
   A = list(A)
   res = []
   for i, a in enumerate(A):
      if key is None: k = a
      else: k = key(a)
      if res and res[-1][0] == k:
         res[-1][-1] += 1
      else:
         res.append([k, i, i+1])
   return [(k, (l, r)) for (k, l, r) in res]


N = int(input())
S = input()

ans = solve(N, S)
print(ans)
0