Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Areas on the Cross-Section Diagram

  Your task is to simulate a flood damage.

  For a given cross-section diagram, reports areas of flooded sections.

  Assume that rain is falling endlessly in the region and the water overflowing from the region is falling in the sea at the both sides.
For example, for the above cross-section diagram, the rain will create floods which have areas of 4, 2, 1, 19 and 9 respectively.

Input

  A string, which represents slopes and flatlands by '/', '\' and '_' respectively, is given in a line. For example, the region of the above example is given by a string "\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\".

output

  Report the areas of floods in the following format:

$A$

$k$ $L_1$ $L_2$ ... $L_k$

  In the first line, print the total area $A$ of created floods.

  In the second line, print the number of floods $k$ and areas $L_i (i = 1, 2, ..., k)$ for each flood from the left side of the cross-section diagram. Print a space character before $L_i$.

Constraints

$1 \leq$ length of the string $\leq 20,000$

Sample Input 1

\\//

Sample Output 1

4
1 4

Sample Input 2

\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\

Sample Output 2

35
5 4 2 1 19 9



Sample input:
\\//


Sample output:
4
1 4

Submission status: Accepted

Solution code:
#coding:utf-8
data = input()
xmax = len(data)
data_list = list(data)
data_list.reverse()
reverse_data = []
for sig in data_list:
    if sig == "\\":
        reverse_data.append("/")
    elif sig == "/":
        reverse_data.append("\\")
    else:
        reverse_data.append(sig)

reverse_data = "".join(reverse_data)


def partialSqu(h, sig):
    if sig == "\\":
        squ = h + 1/2
        h += 1
    elif sig == "/":
        squ = h - 1/2
        h -= 1
    elif sig == "_":
        squ = h
    return squ, h


x_squ_dict = {}
cnt = 0
sw, x, h, totalSqu = 0, 0, 0, 0
for sig in data:
    x += 1
    if sw == 0 and sig == "\\":
        sw = 1
    if sw == 1 :
        squ, h = partialSqu(h, sig)
        totalSqu += squ
        
        if h == 0:
            x_squ_dict[x] = totalSqu
            totalSqu = 0
            sw = 0



keys = x_squ_dict.keys()
sw, x, h, totalSqu = 0, 0, 0, 0
for sig in reverse_data:
    x += 1
    if sw == 0 and sig == "\\" :
        sw = 1
        x_p = xmax - x +1
    if sw == 1 :
        squ, h = partialSqu(h, sig)
        totalSqu += squ            
        if h == 0:
            x_squ_dict[x_p] = totalSqu
            totalSqu = 0
            sw = 0


keys = x_squ_dict.keys()
keys = list(keys)
keys.sort()
squ_list = []
for key in keys:
    squ_list.append(x_squ_dict[key])
    
a = int(sum(squ_list))
print(a)    
squ_list.insert(0,len(keys))

squ_list = " ".join([str(int(num)) for num in squ_list])
print(squ_list)

Submission status: Accepted

Solution code:
s = j = 0
a, b, d = [], [], []

for i, x in enumerate(input()):
    if x == '\\':
        a += [i]
    elif x == '/' and a:
        j = a.pop()
        c = i-j
        s += c

        while b and b[-1] > j:
            c += d.pop()
            b.pop()

        b += [j]
        d += [c]

print(s)
print(len(b), *(d))

Submission status: Accepted

Solution code:
def print_list_split_whitespace(a):
    for x in a[:-1]:
        print(x, end=' ')
    print(a[-1])
    
s = list(input())
st1 = []
st2 = []

for index, c in enumerate(s):
    if c == "\\":
        st1.append(index)
    elif c == "/":
        if len(st1) >= 1:
            pop_index = st1.pop()
            area = index - pop_index
            while True:
                if len(st2) >= 1:
                    ind, pop_area = st2.pop()
                else:
                    st2.append((index, area))
                    break
                if ind < pop_index:
                    st2.append((ind, pop_area))
                    st2.append((index, area))
                    break
                else:
                    area += pop_area

a = 0
k = len(st2)
ls = [k]
for _, s in st2:
    a += s
    ls.append(s)

print(a)
print_list_split_whitespace(ls)

Submission status: Accepted

Solution code:
from sys import stdin
def stdinput():
    return stdin.readline().strip()

def main():
    altitutes = load_data()

    edges = create_edges(altitutes)

    # print(*edges)

    areas = calc_areas(altitutes, edges)

    print(int(sum(areas)))
    print(*([len(areas)] + [*map(int, areas)]))

def load_data():
    A = [0]
    for s in stdinput():
        if s == '\\':
            A.append(A[-1] - 1)
        elif s == '_':
            A.append(A[-1])
        elif s == '/':
            A.append(A[-1] + 1) 
    return A

def create_edges(A):
    st = [(0, None, 0)]
    highest = 0
    for i, a in enumerate(A[1:], 1):
        if st[-1][0] >= a:
            st.append((a, st[-1][2], i))
        else:
            begin = i - 1
            # NOTE: concat edges
            # this operation is performed every upforward(/) step,
            # and previous concated edges have altitute of (a - 1).
            while st[-1][1] != None and st[-1][0] == a - 1 and highest >= a:
                lev, begin, j = st.pop()
            highest = max(highest, a)
            st.append((a, begin, i))
        # print(*st)
    return [*map(lambda e: e[1:], st[1:])]

def calc_areas(A, edges):
    areas = []
    for begin, end in edges:
        area = calc_area(A, begin, end)
        if area > 0:
            areas.append(area)
    return areas    

def calc_area(A, begin, end):
    if A[begin] != A[end]:
        return 0
    b_level = A[begin]
    area = 0
    for l1, l2 in zip(range(begin, end), range(begin+1, end + 1)):
        a1 = A[l1]
        a2 = A[l2]
        area += (b_level - a1 + b_level - a2) * 1 / 2
    return area

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

S = input()

# 各地点の高さを求める
v = {'\\': -1, '_': 0, '/': 1}
h = 0  # 左端の高さ
H = [h]
for s in S:
    h += v[s]
    H.append(h)

# 右部分列の最大値
R = [0] * len(H)
R[-1] = -float('inf')
for i in range(len(R) - 2, -1, -1):
    R[i] = max(R[i+1], H[i+1])

A = []
i = 0
while True:
    # 左端の左斜面をスキップ
    while i < len(S) and S[i] != '\\':
        i += 1

    # 右側の縁と同じ高さまでスキップ
    while i < len(S) and (H[i] > R[i] or S[i] == '_'):
        i += 1

    if i >= len(S):
        break

    # 水たまりの面積を求める
    h = H[i]  # 左端の高さ
    a = 0     # 面積
    while i < len(S):
        a += (h - H[i]) + (H[i] - H[i+1])/2
        i += 1
        if H[i] == h: break
    A.append(int(a))

print(sum(A))
print(' '.join(map(str, [len(A)] + A)))

Submission status: Accepted

Solution code:
s=j=0
a=[];b=[];d=[]
for i,x in enumerate(input()):
    if x=='\\':a+=[i]
    elif x=='/' and a:
        j=a.pop()
        c=i-j;s+=c
        while b and b[-1]>j:c+=d.pop();b.pop()
        b+=[j];d+=[c]
print(s)
print(len(b),*(d))

Submission status: Accepted

Solution code:
x = input()
y = []
z = []
n = 0
for i in range(len(x)):
    if x[i] == '\\':
        if n:
            y.append(n)
            n = 0
            if z:
                z.append(-1)
        z.append(i)
    elif x[i] == '/':
        if z:
            while True:
                p = z.pop()
                if p == -1:
                    n += y.pop()
                else:
                    break
            n += i-p
    else:
        pass
if n:
    y.append(n)
for j in range(y.count(0)):
    y.remove(0)
print(sum(y))
print(len(y), *y)

Submission status: Accepted

Solution code:
input_string = input()
total_area = 0
num_lake = 0
lake_areas = []

v_lakes = [] # (湖の始まりidx, 湖の面積)
idx_stack = [] #地形管理

for i, c in enumerate(input_string):
    if c == "\\":
        idx_stack.append(i)
    elif c == "/" and idx_stack:
        poped_i = idx_stack.pop()
        total_area += i - poped_i
        tmp_area = i - poped_i
        while v_lakes and v_lakes[-1][0] > poped_i:
            tmp_area += v_lakes.pop()[1]
            
        v_lakes.append((poped_i, tmp_area))
#print(v_lakes)

print(total_area)
ans = [area[1] for area in v_lakes] 
print(len(v_lakes), *ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
A = S()
Down = deque([])
S = deque([])

for i in range(len(A)):
    if A[i] == '\\':
        Down.append(i)
    elif A[i] == '/' and len(Down) != 0:
        j = Down.pop()
        a = i - j
        while len(S) > 0 and S[-1][0] > j:
            a += S.pop()[1]
        S.append((j, a))
ans = []
for i in range(len(S)):
    ans.append(S[i][1])
print(sum(ans))
ans.insert(0, len(ans))
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
class stack():
    def __init__(self):
        self.S = []
        
    def push(self, x):
        self.S.append(x)
        
    def pop(self):
        return self.S.pop()
        
    def isEmpty(self):
        if len(self.S) == 0:
            return True
        else:
            return False

areas = input()

S1 = stack()
S2 = stack()

for i, info in enumerate(areas):
    if info == '/':
        if S1.isEmpty():
            continue
        left = S1.pop()
        menseki = i - left
        while True:
            if S2.isEmpty():
                S2.push([menseki, left])
                break
            if S2.S[-1][1] < left:
                S2.push([menseki, left])
                break
            menseki += S2.pop()[0]
    elif info == '\\':
        S1.push(i)

ans = [m[0] for m in S2.S]
print(sum(ans))
if len(ans) == 0:
    print(len(ans))
else:
    print(len(ans), ' '.join(list(map(str, ans))))

Submission status: Accepted

Solution code:
a, b, d = [], [], []
amount = 0
for i, x in enumerate(input()):
    if x == '\\':
        a += [i]
    elif x == '/' and a:
        j = a.pop()
        pool = i - j
        amount += pool
        while b and b[-1] > j:
            pool += d.pop()
            b.pop()
        b.append(j)
        d.append(pool)
print(amount)
print(len(b), *d)

Submission status: Accepted

Solution code:
s1 = []
s2 = []
a = 0
s = input()
for i in range(len(s)):
    if s[i] == "\\":
        s1.append(i)
    elif s[i] == "/" and len(s1)>0:
        j = s1.pop()#position of nearest \
        a += i-j
        a_splt = i-j
        while(len(s2) > 0 and s2[-1][0] > j):
            a_splt += s2.pop()[1]
        s2.append([j, a_splt])

print(a)
ans = ""
ans += str(len(s2))
for area in s2:
    ans += " " + str(area[1])
print(ans)

Submission status: Accepted

Solution code:
Input = input()

v_lakes =[]  #個々の湖の面積管理用のstack
idx_stack = [] #地形のindex管理用のstack

for i, c in enumerate(Input):
    if c == "\\":
        idx_stack.append(i)
    elif c == "/" and idx_stack:
        j = idx_stack.pop()
        v = i - j

        while v_lakes and j < v_lakes[-1][0]:
            v += v_lakes.pop()[1]

        v_lakes.append((j,v))

ans = [len(v_lakes)]
v = [v[1] for v in v_lakes]
ans.extend(v)

print(sum(v))
print(*ans)

Submission status: Accepted

Solution code:
def print_puddle(puddle):
    n = len(puddle)
    if n > 0:
        print(n, end=' ')
    else:
        print(n)
    for i in range(n):
        if i != n - 1:
            print(puddle[i][1], end=' ')
        else:
            print(puddle[i][1])



def solve(A):
    left = []
    puddle = []
    sum_all = 0
    for i, a in enumerate(A):
        if a == '\\':
            left.append(i)
        elif a == '/' and len(left) > 0:
            left_i = left.pop()
            a = i - left_i
            sum_paddle = i - left_i
            sum_all += a
            while len(puddle) and puddle[-1][0] > left_i:
                tmp = puddle.pop()
                sum_paddle += tmp[1]

            puddle.append((left_i, sum_paddle))
    print(sum_all)
    print_puddle(puddle)


def main():
    A = list(input())

    solve(A)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    from operator import itemgetter

    s = input()

    tot = 0
    areas = []

    dq = deque()
    for i, c in enumerate(s):
        # print(c, end='')

        if c == '\\':
            dq.append(i)
        elif c == '/':
            if dq:
                j = dq.pop()
                a = i - j
                tot += a

                while areas and areas[-1][0] > j:
                    a += areas.pop()[1]
                areas.append((i, a))

    print(tot)
    print(len(areas), *map(itemgetter(1), areas))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    
    from collections import deque

    s = input()
    s1 = deque([])
    s2 = deque([])

    sum_ = 0
    
    for i, ch in enumerate(s):
        if ch == '\\' :
            s1.append(i)
            
        elif ch =='/' and len(s1) > 0:
            j = s1.pop()
            sum_ += i - j
            a = i- j
            while len(s2) > 0 and s2[-1][0] > j:
                a += s2.pop()[1]
            s2.append([j, a])
            
    ans = []
    
    while len(s2)>0:
        ans.append(s2.pop()[1])
        
    ans.reverse()
    print(sum(ans))
    ans.insert(0, len(ans))
    
    print(' '.join(map(str, ans)))

    
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
downs, ponds = [], []
for i, s in enumerate(input()):
  if s == "\\":
    downs.append(i)
  elif s == "/" and downs:
    i_down = downs.pop()
    area = i - i_down
    while ponds and ponds[-1][0] > i_down:
      area += ponds.pop()[1]
    ponds.append([i_down, area])
print(sum(p[1] for p in ponds))
print(len(ponds), *(p[1] for p in ponds))

Submission status: Accepted

Solution code:
s=[]
p=[]
a=i=0
for c in input():
 if"\\"==c:s+=[i]
 elif"/"==c and s:
  j=s.pop()
  t=i-j
  a+=t
  while p and p[-1][0]>j:t+=p[-1][1];p.pop()
  p+=[(j,t)]
 i+=1
print(a)
if p:print(len(p),*list(zip(*p))[1])
else:print(0)

Submission status: Accepted

Solution code:
from collections import deque

areas = input()
S1 = deque([])
S2 = deque([])

sum_ = 0

for i,ch in enumerate(areas):
    if ch == "\\":
        S1.append(i)
    elif ch == "/" and len(S1) > 0:
        j = S1.pop()
        sum_ += i-j
        a = i-j
        while len(S2) > 0 and S2[-1][0] > j:
            a += S2.pop()[1]
        S2.append([j,a])

ans = []
while len(S2) > 0:
    ans.append(S2.pop()[1])

ans.reverse()

A = sum(ans)
print(A)

ans.insert(0,len(ans))
L = map(str,ans)
print(" ".join(L))

Submission status: Accepted

Solution code:
ch = input()
stk1 = []
stk2 = []
ttlar = 0
for i, c in enumerate(ch):
    if c == '\\':
        stk1.append(i)
    elif c == '/' and stk1 != []:
        j = stk1.pop()
        ttlar += i - j
        lar = i - j
        while stk2 != [] and stk2[-1][0] > j:
            lar += stk2.pop()[1]
        stk2.append([j, lar])
print(ttlar)
ans = [len(stk2)]
ans[1:1] = [stk2[i][1] for i in range(len(stk2))]
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
my_str = input()

s1 = []
s2 = []
sum = 0

for idx, letter in enumerate(my_str):
    if letter == '\\':
        s1.append(idx)

    elif letter == '/' and s1:
        jdx = s1.pop()
        a = idx -jdx
        sum += a

        while s2 and s2[-1][0] > jdx:
            a += s2.pop()[1]
        s2.append([jdx, a])

print(sum)
print(len(s2), *(a for _, a in s2))

Submission status: Accepted

Solution code:
from collections import deque
import sys

# downには「\」の数を入れる
down = deque()
edge = deque()
pool = deque()

for i, j in enumerate(sys.stdin.readline().splitlines()[0]):
    if j == "\\":
        down.append(i)
    # downが空でなく、かつ右斜面の場合
    elif down and j == "/":
        left = down.pop()
        area = i - left

        # edgeが空になるまで
        while edge:
            # 右端が
            if edge[-1] < left:
                break
            edge.pop()
            area += pool.pop()

        edge.append(left)
        pool.append(area)

print(sum(pool))
print(len(pool), *pool)

Submission status: Accepted

Solution code:
from collections import deque

s1 = deque()
s2 = deque()

s = input()
totalarea = 0

for i,c in enumerate(s):
    if c == '\\':
        s1.append(i)
    elif s1 and c == '/':
        j = s1.pop()
        area = i - j
        totalarea +=  area
        subarea = area
        while s2 and s2[-1][0] > j:
            subarea += s2[-1][1]
            s2.pop()
        s2.append((j, subarea))

print(totalarea)
print(len(s2), end='')
if s2:
    print(" ",end="")
    areas = [str(puddle[1]) for puddle in s2]
    print(" ".join(areas))
else:
    print("")

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque
import copy

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def calc_water(u, l, h):
    return ((u + l) * h) // 2


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    stack = []

    water = []
    sum = 0
    for i in range(len(S)):
        s = S[i]
        if s == '\\':
            stack.append(i)
        elif s == '/' and len(stack) > 0:
            j = stack.pop()
            sum += i - j
            area = i - j
            while len(water) > 0 and water[-1][0] > j:
                w = water.pop()
                area += w[1]
            water.append([j, area])

    ret = []
    for i, w in water:
        ret.append(w)
    print(sum)
    print(len(ret), *ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

codes = input()

s1 = deque([])
s2 = deque([])

sums = 0
for idx1, ch in enumerate(codes):
    if ch == '\\':
        s1.append(idx1)
    elif ch == '/' and len(s1) > 0:
        idx2 = s1.pop()
        area = idx1 - idx2
        sums += area
        while len(s2) > 0 and s2[-1][0] > idx2:
            area += s2.pop()[1]
        s2.append([idx2, area])

output = []
while len(s2) > 0:
    output.append(s2.pop()[1])
output.reverse()
print(sum(output))
output.insert(0, len(output))
print(" ".join(map(str, output)))

Submission status: Accepted

Solution code:
from collections import deque

S = input()

bs_idx = deque()
areas = []
for idx, s in enumerate(S):
    if s == "\\":
        bs_idx.append(idx)
    if s == "/":
        if bs_idx:
            left_idx = bs_idx.pop()
            areas.append([left_idx, idx - left_idx])

areas.sort()

if not areas:
    print(0)
    print(0)
else:
    ans = []
    i = 0
    while True:
        if i == len(areas):
            break
        area = areas[i][1]
        tmp = areas[i][0] + area
        while True:
            i += 1
            if i != len(areas) and areas[i][0] < tmp:
                area += areas[i][1]
            else:
                ans.append(area)
                break

    print(sum(ans))
    print(len(ans), " ".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

S = input().strip()

stack = []
ponds = []

for idx, s in enumerate(S):
    if s == "\\":
        stack.append(idx)
    elif s == "/" and stack:
        _first = stack.pop()
        pond = idx - _first
        ponds.append((_first, pond))

    # concatnate ponds
    while len(ponds) > 1:
        _cur, _size = ponds.pop()
        _prev, _prev_size = ponds.pop()

        if _cur < _prev:
            ponds.append((_cur, _prev_size + _size))
        else:
            ponds.append((_prev, _prev_size))
            ponds.append((_cur, _size))
            break

ans = []
for idx, size in ponds:
    ans.append(size)
if not ans:
    print(0)
    print(0)
else:
    print(sum(ans))
    print("{} ".format(len(ans)) + " ".join([str(s) for s in ans]))

Submission status: Accepted

Solution code:
string = input()

h = 0
A = [h]
for c in string:
    if c == "/": h += 1
    elif c == "\\": h -= 1
    A.append(h)

flg = False
ans1 = []
ans2 = []

forward = True
while len(A) > 1:
    h = 0
    B = [0]

    for i in range(len(A) - 1):
        if not flg: B = [0]

        d = A[i + 1] - A[i]
        if d < 0: flg = True
        h += d

        if h <= 0:
            B.append(h)

            if h == 0:
                if len(B) > 2:
                    if forward: ans1.append(abs(sum(B)))
                    else: ans2.append(abs(sum(B)))
                B = []
                flg = False
        else:
            h = 0

    A = B.copy()
    A.reverse()
    forward = (forward + 1) % 2

ans2.reverse()
ans = ans1 + ans2

print(sum(ans))
print(len(ans), *ans)

Submission status: Accepted

Solution code:
from collections import deque

stack = []
stack2 = []

input_line = input().rstrip()

menseki = 0

for i, s in enumerate(input_line):
    if s == "\\":
        stack.append(i)
    elif s == "/" and len(stack) > 0:
        j = stack.pop()
        menseki += (i - j)
        temp_menseki = 0
        while len(stack2) > 0 and j < stack2[-1][0]:
            temp_menseki += stack2.pop()[1]
                    
        stack2.append([j, temp_menseki + (i - j)])

print(menseki)
if len(stack2) > 0:
    print(len(stack2), " ".join([str(j[1]) for j in stack2]))
else:
    print("0")

Submission status: Accepted

Solution code:
g = list(input())

sum, d, r, p = 0, 0, 0, 0
f = 0
lake_list = []

for c in g:
    if c == "\\":
        if f == 0:
            f, d, r = 1, 1, 1
        else:
            d += 1
            r += (1 + (d-1))
    elif c == "_":
        if f == 1:
            r += d
    else:
        if f == 1:
            d -= 1
            r += d
            if d == 0:
                f = 0
                sum += r
                lake_list.append([p, r])
                r = 0
    p += 1

d, r, p = 0, 0, len(g)-1
f = 0
g.reverse()

for c in g:
    if c == "/":
        if f == 0:
            f, d, r = 1, 1, 1
            pr = p
        else:
            d += 1
            r += (1 + (d-1))
    elif c == "_":
        if f == 1:
            r += d
    else:
        if f == 1:
            d -= 1
            r += d
            if d == 0:
                if [pr, r] not in lake_list:
                    sum += r
                    lake_list.append([pr, r])
                f = 0
                r = 0
    p -= 1

lake_list.sort()
print(sum)
print(len(lake_list), end="")
i = 0
while i != len(lake_list):
    print(" {}".format(lake_list[i][1]), end="")
    i += 1
print()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
from collections import deque

input = sys.stdin.readline


def main():
    S = input().rstrip()

    stack = deque()
    M = []
    for i, s in enumerate(S):
        if s == "/":
            if len(stack) == 0:
                pass
            else:
                j = stack.pop()
                M.append((j, i))
        elif s == "\\":
            stack.append(i)
        else:
            pass

    M.sort(key=itemgetter(0))
    L = []
    r = -1
    for i, j in M:
        if r < i:
            r = j
            L.append(j - i)
        else:
            L[-1] += (j - i)

    A = sum(L)
    k = len(L)

    print(A)
    if k == 0:
        print(k)
    else:
        print(" ".join([str(k), " ".join(map(str, L))]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def areas(updown: str):
    stack1, stack2 = [], []

    for i, c in enumerate(updown):
        if c == "\\":
            stack1.append(i)
        elif c == "/":
            if len(stack1) == 0:
                continue

            match = stack1.pop()

            # ToDo
            total = 0
            while stack2 and match < stack2[-1][0]:
                _, x = stack2.pop()
                total += x

            total += i - match
            stack2.append((match, total))

        elif c == "_":
            # 何もする必要がない
            pass
        else:
            raise Exception("Invalid Input")

    print(sum(x for _, x in stack2))
    print("{} {}".format(len(stack2), " ".join([str(x) for _, x in stack2])).strip())


# in1 = r"\\//"
# in2 = r"\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/" + "\\"

s = input().strip()
areas(s)

Submission status: Accepted

Solution code:
s=input()
d_in={'/':1,'\\':-1,'_':0}
stack_h=[]
pairs_x=[]
for i in range(len(s)):
  if d_in[s[i]]==-1:
    stack_h.append(i)
  elif d_in[s[i]]==1:
    if len(stack_h)!=0:
      pairs_x.append([stack_h.pop(),i+1])
stack_ans=[]
for i in range(len(pairs_x)):
  pair_i=pairs_x.pop()
  if len(stack_ans)==0:
    stack_ans.append(pair_i)
  elif pair_i[1]<=stack_ans[-1][0]:
    stack_ans.append(pair_i)
area=[0]*len(stack_ans)
sum_area=0
for i in range(len(stack_ans)):
  p=stack_ans.pop()
  h=0
  for j in range(p[0],p[1]):
    area[i]+=h
    h-=d_in[s[j]]
  sum_area+=area[i]

print(sum_area)
if len(area)==0:
  print(0)
else:
  print(len(area),end=' ')
  print(' '.join(map(str,area)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    S = input()
    pair = []
    stack = [('%',-1)]
    for j,s in enumerate(S):
        if s == '/':
            if stack[-1][0] == '\\':
                i = stack[-1][1]
                stack.pop()
                pair.append((i,j))
        elif s == '_':
            continue
        else:
            stack.append((s,j))
    
    pond = []
    tot = 0
    k = len(pair) - 1
    while  k >= 0:
        fin = pair[k][0] - 1
        area = 0
        while k >= 0 and fin < pair[k][0]:
            area += pair[k][1] - pair[k][0]
            k -= 1
        pond.append(area)
        tot += area
    pond.append(len(pond))

    print(tot)
    print(*pond[::-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s=0
j=0
a=[]
k=[]
l=[]
for i,x in enumerate(input()):
    if x=='\\':
        a+=[i]
    elif x=='/' and a:
        j=a.pop()
        y=i-j;s+=y
        while k and k[-1]>j:
            y+=l.pop()
            k.pop()
        k+=[j]
        l+=[y]
print(s)
print(len(k),*(l))

Submission status: Accepted

Solution code:
S = input()

# ■のマスは2, ▲のマスは1でカウントする

def scan_forward(F:list, S):

    depth = 0  # 深さ（開始点を基準）
    start = 0  # 「池」が始まった高さ
    is_pond = True  # 池が始まっているか？

    for s in S:
        if s == '\\':  # 下り
            if not is_pond:
                is_pond = True
                start = depth
            depth -= 1
            F.append(2*(start - depth) - 1)
            continue

        if s == "/":  # 上り
            depth += 1
            if start < depth:  # 池の開始位置より高くなった場合
                is_pond = False
                F.append(0)
                continue
            else:
                F.append(2*(start - depth) + 1)

        if s == "_":
            if is_pond:
                F.append(2*(start - depth))
            else:
                F.append(0)

def scan_backward(B:list, S):
    
    depth = 0  # 深さ（開始点を基準）
    start = 0  # 「池」が始まった高さ
    is_pond = True  # 池が始まっているか？

    for s in S:
        if s == '/':  # 下り
            if not is_pond:
                is_pond = True
                start = depth
            depth -= 1
            B.append(2*(start - depth) - 1)
            continue

        if s == "\\":  # 上り
            depth += 1
            if start < depth:  # 現在地が池の開始位置より高い場合
                is_pond = False # 「池」終了
                B.append(0)
                continue
            B.append(2*(start - depth) + 1)

        if s == "_":
            if is_pond:
                B.append(2*(start - depth))
            else:
                B.append(0)

def count_pond(FB):
    
    P = []

    is_pond = False
    count = 0
    amount = 0
    all_amount = 0
    for i in range(len(FB)):
        all_amount += FB[i]
        if is_pond:  # 池の途中
            amount += FB[i]
            if FB[i] == 1:
                is_pond = False  # ここで一旦終了
                P.append(amount//2)
        else:  # 池でなくなった場合
            if FB[i] == 0: continue
            count += 1
            is_pond = True
            amount = FB[i]
    
    return all_amount//2, count, P

F = []
scan_forward(F, S)

B = []
scan_backward(B, reversed(S))
B.reverse()
# print(F)  # 順方向にスキャンした結果
# print(B)  # 逆方向にスキャンした結果

FB = [0]*len(F)
# print(len(F), len(B))

for i in range(len(F)):
    FB[i] = min(F[i], B[i])


# print(FB)  # 水量

aa, k, P = count_pond(FB)
print(aa)
if k == 0:
    print(k)
else:
    print(k, " ".join(list(map(str, P))))

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
A = input()

total = 0
total_each = deque()
S1 = deque()
S2 = deque()
for j,a in enumerate(A):
    #print('j = {}, S2 = {}'.format(j,S2))
    if a == '\\':
        S1.append(j)
    elif a=='/':
        try:
            i = S1.pop()
            val_new = j-i
            total += val_new
            
            if len(S2)==0:
                S2.append((i,val_new))
                continue
            
            while True:
                if len(S2)>0:
                    a,val = S2[-1]
                    if a<i:
                        S2.append((i, val_new))
                        break
                    elif i<a:
                        _ = S2.pop()
                        val_new = val + val_new
                else:
                    S2.append((i,val_new))
                    break
        except:
            pass
print(total)
ans = [len(S2)]
for _ in range(len(S2)):
    a,val = S2.popleft()
    ans.append(val)
print(*ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from collections import deque
    str = input()
    stack1,stack2 = deque([]),deque([])
    sum = 0

    for i in range(len(str)):
        if str[i] == '\\':
            stack1.append(i)
        elif str[i] == '/':
            if stack1 != deque([]):
                x = stack1.pop()
                stack2.append([x,i-x])

        while len(stack2) >= 2 and stack2[len(stack2) - 2][0] > stack2[len(stack2) - 1][0]:
            a = stack2.pop()
            b = stack2.pop()
            stack2.append([a[0],a[1]+b[1]])

    #全面積算出、出力
    for i in range(len(stack2)):
        sum += stack2[i][1]
    print(sum)
    if len(stack2) > 0:
        print(len(stack2),end = " ")
    else:
        print(len(stack2))
    for i in range(len(stack2)):
        if i == len(stack2) - 1:
            print(stack2[i][1])
        else:
            print(stack2[i][1],end = " ")

Submission status: Accepted

Solution code:
ch = input()
area_idx = []
area = []
for i, c in enumerate(ch):
    if c == '\\':
        area_idx.append(i)
    elif c == '/' and area_idx:
        j = area_idx.pop() 
        v = i-j
        while area and j < area[-1][0]:
            v += area.pop()[1]
        area.append((j, v))
n = len(area)
a = [v[1] for v in area]
print(sum(a))
print(n, *a)