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: Time Limit Exceeded

Solution code:
class Cell(object):
    def __init__(self, direction, x, y):
        self.direction = direction
        self.x = x
        self.y = y
        self.is_pond = False
        self.start_of_pond = False
        self.end_of_pond = False

    def get_area(self, pond_height):
        h = pond_height - self.y + 1
        if self.direction == 'f':
            return h - 1
        else:
            return h - 0.5

    @property
    def char(self):
        if self.direction == 'd':
            return '/'
        elif self.direction == 'u':
            return '\\'
        elif self.direction == 'f':
            return '|'

class Area(object):
    def __init__(self):
        self.cells = {}
        self.before_c = ''
        self.x = 0
        self.height = 0
        self.lowest = 0
        self.pond_area = []

    def put(self, c):
        if c == '\\':
            if self.before_c == '\\':
                self.height -= 1
            self.cells[self.x] = Cell('d', self.x, self.height)
        elif c == '/':
            if self.before_c == '/' or self.before_c == '_':
                self.height += 1
            self.cells[self.x] = Cell('u', self.x, self.height)
        elif c == '_':
            if self.before_c == '\\':
                self.height -= 1
            self.cells[self.x] = Cell('f', self.x, self.height)
        
        if self.cells[self.x].y < self.lowest:
            self.lowest = self.cells[self.x].y
        self.x += 1
        self.before_c = c

    def adjust_height(self):
        for i, c in self.cells.items():
            c.y -= self.lowest
    
    def is_pond(self):
        start_of_pond = None
        ponds = []
        for i_start in range(len(self.cells)):
            c_start = self.cells[i_start]

            if c_start.is_pond:
                ponds.append(c_start)
            if c_start.direction == 'u':
                if start_of_pond:
                    if start_of_pond.y == c_start.y:
                        start_of_pond = None
                        c_start.end_of_pond = True
                        self.pond_area.append(self.calc_area(ponds))
                        ponds = []
                continue
            if c_start.direction == 'f' and 0 == i_start:
                continue
            if c_start.direction == 'f' and not self.cells[i_start - 1].is_pond:
                continue
            if c_start.direction == 'f' and self.cells[i_start - 1].end_of_pond:
                continue

            for i_end in range(i_start+1, len(self.cells)):
                if c_start.is_pond:
                    break
                c_end = self.cells[i_end]
                if c_start.y <= c_end.y:
                    if c_end.direction == 'u':
                        for i in range(c_start.x, c_end.x+1):
                            self.cells[i].is_pond = True
                    elif c_end.direction == 'd':
                        continue
                    elif c_end.direction == 'f':
                        continue
                    break
            if not start_of_pond and c_start.is_pond:
                c_start.start_of_pond = True
                start_of_pond = c_start
            if c_start.is_pond and not c_start in ponds:
                ponds.append(c_start)

    def calc_area(self, ponds):
        area = 0
        height = ponds[0].y
        for c in ponds:
            area += c.get_area(height)
        return int(area)

    def show(self):
        for i, c in self.cells.items():
            p = 'p' if c.is_pond else ' '
            e = 'E' if c.end_of_pond else ''
            s = 'S' if c.start_of_pond else ''
            print('{0:02d}'.format(i) + p + c.char * (c.y+1) + e + s)

def run():
    area = Area()
    for l in input():
        area.put(l)
    area.adjust_height()
    area.is_pond()
    # area.show()
    print(sum(area.pond_area))
    if area.pond_area:
        print(len(area.pond_area), ' '.join([str(a) for a in area.pond_area]))
    else:
        print(0)

if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:
class Cell(object):
    def __init__(self, direction, x, y):
        self.direction = direction
        self.x = x
        self.y = y
        self.is_pond = False
        self.start_of_pond = False
        self.end_of_pond = False

    def get_area(self, pond_height):
        h = pond_height - self.y + 1
        if self.direction == 'f':
            return h - 1
        else:
            return h - 0.5

    @property
    def char(self):
        if self.direction == 'd':
            return '/'
        elif self.direction == 'u':
            return '\\'
        elif self.direction == 'f':
            return '|'

class Area(object):
    def __init__(self):
        self.cells = {}
        self.before_c = ''
        self.x = 0
        self.height = 0
        self.lowest = 0
        self.pond_area = []

    def put(self, c):
        if c == '\\':
            if self.before_c == '\\':
                self.height -= 1
            self.cells[self.x] = Cell('d', self.x, self.height)
        elif c == '/':
            if self.before_c == '/' or self.before_c == '_':
                self.height += 1
            self.cells[self.x] = Cell('u', self.x, self.height)
        elif c == '_':
            if self.before_c == '\\':
                self.height -= 1
            self.cells[self.x] = Cell('f', self.x, self.height)
        
        if self.cells[self.x].y < self.lowest:
            self.lowest = self.cells[self.x].y
        self.x += 1
        self.before_c = c

    def adjust_height(self):
        for i, c in self.cells.items():
            c.y -= self.lowest
    
    def is_pond(self):
        start_of_pond = None
        ponds = []
        for i_start in range(len(self.cells)):
            c_start = self.cells[i_start]

            if c_start.is_pond:
                ponds.append(c_start)
            if c_start.direction == 'u':
                if start_of_pond:
                    if start_of_pond.y == c_start.y:
                        start_of_pond = None
                        c_start.end_of_pond = True
                        self.pond_area.append(self.calc_area(ponds))
                        ponds = []
                continue
            if c_start.direction == 'f' and 0 == i_start:
                continue
            if c_start.direction == 'f' and not self.cells[i_start - 1].is_pond:
                continue
            if c_start.direction == 'f' and self.cells[i_start - 1].end_of_pond:
                continue
            if c_start.direction == 'd' or c_start.direction == 'f':
                if c_start.is_pond:
                    continue
    
            for i_end in range(i_start+1, len(self.cells)):
                c_end = self.cells[i_end]
                if c_start.y <= c_end.y:
                    if c_end.direction == 'u':
                        for i in range(c_start.x, c_end.x+1):
                            self.cells[i].is_pond = True
                    elif c_end.direction == 'd':
                        continue
                    elif c_end.direction == 'f':
                        continue
                    break
            if not start_of_pond and c_start.is_pond:
                c_start.start_of_pond = True
                start_of_pond = c_start
            if c_start.is_pond and not c_start in ponds:
                ponds.append(c_start)

    def calc_area(self, ponds):
        area = 0
        height = ponds[0].y
        for c in ponds:
            area += c.get_area(height)
        return int(area)

    def show(self):
        for i, c in self.cells.items():
            p = 'p' if c.is_pond else ' '
            e = 'E' if c.end_of_pond else ''
            s = 'S' if c.start_of_pond else ''
            print('{0:02d}'.format(i) + p + c.char * (c.y+1) + e + s)

def run():
    area = Area()
    for l in input():
        area.put(l)
    area.adjust_height()
    area.is_pond()
    # area.show()
    print(sum(area.pond_area))
    if area.pond_area:
        print(len(area.pond_area), ' '.join([str(a) for a in area.pond_area]))
    else:
        print(0)

if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:
class Cell(object):
    def __init__(self, direction, x, y):
        self.direction = direction
        self.x = x
        self.y = y
        self.is_pond = False
        self.never_pond = False
        self.start_of_pond = False
        self.end_of_pond = False

    def get_area(self, pond_height):
        h = pond_height - self.y + 1
        if self.direction == 'f':
            return h - 1
        else:
            return h - 0.5

    @property
    def char(self):
        if self.direction == 'd':
            return '/'
        elif self.direction == 'u':
            return '\\'
        elif self.direction == 'f':
            return '|'

class Area(object):
    def __init__(self):
        self.cells = {}
        self.before_c = ''
        self.x = -1
        self.height = 0
        self.lowest = 0
        self.highest = 0
        self.higher = 0
        self.pond_area = []
        self.reverse = False

    def put(self, c):
        self.x += 1
        if c == '\\':
            if self.before_c == '\\':
                self.height -= 1
            self.cells[self.x] = Cell('d', self.x, self.height)
        elif c == '/':
            if self.before_c == '/' or self.before_c == '_':
                self.height += 1
            self.cells[self.x] = Cell('u', self.x, self.height)
        elif c == '_':
            if self.before_c == '\\':
                self.height -= 1
            self.cells[self.x] = Cell('f', self.x, self.height)
        
        if self.cells[self.x].y < self.lowest:
            self.lowest = self.cells[self.x].y
        if self.highest < self.cells[self.x].y:
            self.highest = self.cells[self.x].y
        self.before_c = c

    def adjust_height(self):
        self.highest -= self.lowest
        for i, c in self.cells.items():
            c.y -= self.lowest
            if self.higher < c.y and c.y < self.highest:
                if c.direction != 'd':
                    self.higher = c.y
    
    def is_pond(self):
        start_of_pond = None
        ponds = []
        for i_start in range(len(self.cells)):
            c_start = self.cells[i_start]
            if c_start.is_pond:
                ponds.append(c_start)
            if c_start.direction == 'u':
                if start_of_pond:
                    if start_of_pond.y == c_start.y:
                        start_of_pond = None
                        c_start.end_of_pond = True
                        self.pond_area.append(self.calc_area(ponds))
                        ponds = []
                continue
            if c_start.direction == 'f' and 0 == i_start:
                continue
            if c_start.direction == 'f' and not self.cells[i_start - 1].is_pond:
                continue
            if c_start.direction == 'f' and self.cells[i_start - 1].end_of_pond:
                continue
            if c_start.direction == 'd' or c_start.direction == 'f':
                if c_start.is_pond:
                    continue
            if c_start.direction == 'd' and self.higher > 0 and self.higher < c_start.y and c_start.y < self.highest:
                continue
            
            for i_end in range(i_start+1, len(self.cells)):
                c_end = self.cells[i_end]
                if c_start.y <= c_end.y:
                    if c_end.direction == 'u':
                        for i in range(c_start.x, c_end.x+1):
                            self.cells[i].is_pond = True
                    elif c_end.direction == 'd':
                        continue
                    elif c_end.direction == 'f':
                        continue
                    break

            if not start_of_pond and c_start.is_pond:
                c_start.start_of_pond = True
                start_of_pond = c_start
            if c_start.is_pond and not c_start in ponds:
                ponds.append(c_start)

    def calc_area(self, ponds):
        area = 0
        height = ponds[0].y
        for c in ponds:
            area += c.get_area(height)
        return int(area)

    def show(self):
        for i, c in self.cells.items():
            p = 'p' if c.is_pond else ' '
            e = 'E' if c.end_of_pond else ''
            s = 'S' if c.start_of_pond else ''
            print('{0:02d}'.format(i) + p + c.char * (c.y+1) + e + s)

def run():
    area = Area()
    for l in input():
        area.put(l)
    area.adjust_height()
    area.is_pond()
    # area.show()
    print(sum(area.pond_area))
    if area.pond_area:
        print(len(area.pond_area), ' '.join([str(a) for a in area.pond_area]))
    else:
        print(0)

if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
from collections import deque

if __name__ == "__main__":
    slopes = input()
    total_area = 0
    slope_queue = deque()
    area_queue = deque()

    for i, slope in enumerate(slopes):
        if slope == '\\':
            slope_queue.append(i)
        elif slope == '/' and len(slope_queue) != 0:
            target = slope_queue.pop()
            area = i - target
            total_area += area
            if len(area_queue) == 0:
                area_queue.append((target, area))
            else:
                temp_area = area
                while True:
                    target_area = area_queue.pop()
                    if target < target_area[0]:
                        temp_area += target_area[1]
                        if len(area_queue) == 0:
                            area_queue.append((target, temp_area))
                            break
                    else:
                        area_queue.append(target_area)
                        area_queue.append((target, temp_area))
                        break

    print(total_area)
    if len(area_queue) == 0:
        print(len(area_queue), end='\n')
    else:
        print(len(area_queue), end=' ')
    for i, area in enumerate(area_queue):
        if i < len(area_queue) - 1:
            print(area[1], end=' ')
        else:
            print(area[1], end='\n')

Submission status: Accepted

Solution code:
def calcAreas(sections):
    areas = []

    for s in sections:
        if len(s) <= 1:
            continue;

        areas.append(toArea(s))

    return areas

def toArea(section):
    a = 0
    b, _ = section[0]

    for s, e in section:
        a += (max(s, e) - b) - (0.5 if s != e else 0)

    return int(a)

def toDelta(p):
    if '/' == p:
        return -1
    if '\\' == p:
        return 1
    return 0

def toPaths(path):
    h = 0
    ph = 0
    paths = []

    for p in path:
        h += toDelta(p)
        paths.append((ph,h))
        ph = h

    return paths

def update(sections):
    [(lf, ll)] = sections.pop()

    n = None

    for i in range(len(sections)-1, -1, -1):
        if sections[i][0][0] == ll:
            n = i
            break

    if n == None:
        sections.append([(lf, ll)])
        return False

    lst = [(lf, ll)]
    for i in range(len(sections)-1, n-1, -1):
        s = sections.pop()
        lst = s + lst

    sections.append(lst)
    return True

def main():
    paths = toPaths(input())

    prev = -1
    sections = []

    prev_update = True

    for f, l in paths:
        sections.append([(f, l)])
        if l < prev:
            if prev_update:
                prev_update = update(sections)
        else:
            prev_update = True

        prev = l

    areas = calcAreas(sections)
    l = len(areas)

    print(sum(areas))
    print(l, end='')
    if l > 0:
        print(' {}'.format(' '.join([str(x) for x in areas])), end='')
    print()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
down = []
puddles = []
ans = 0

for i, s in enumerate(input()):
    if s == '\\':
        down.append(i)
    elif s == '/' and down:
        l = down.pop()
        # 累積和
        a = i - l
        # 高さが上から見ていった時下向きの斜面が今のペアの斜面より右にきている
        # -> 次の池
        while puddles and puddles[-1][0] > l:
            a += puddles.pop()[1]
        puddles.append((l, a))


print(sum(a for l, a in puddles))
print(len(puddles), *(a for l, a in puddles))

Submission status: Accepted

Solution code:
arr = list(input())
down = list()
areas = list()

for i, el in enumerate(arr):
    if el == "\\":
        down.append(i)
    elif el == "/" and not len(down) == 0:
        start_ind = down.pop()
        area = i - start_ind
        while len(areas) > 0 and areas[-1][0] > start_ind:
            area += areas.pop()[1]
        areas.append((start_ind, area))
    # print("LOOP: {}".format(i))
    # print("DOWN INDICES")
    # print(down)
    # print("AREAS")
    # print(areas)
    # print()

areas = [areas[i][1] for i in range(len(areas))]
print(sum(areas))
if len(areas) == 0:
    print("0")
else:
    print(len(areas), " ".join(map(str,areas)))

Submission status: Accepted

Solution code:
arr = list(input())
down = list()
areas = list()

for i, el in enumerate(arr):
    if el == "\\":
        down.append(i)
    elif el == "/" and not len(down) == 0:
        start_ind = down.pop()
        area = i - start_ind
        while len(areas) > 0 and areas[-1][0] > start_ind:
            area += areas.pop()[1]
        areas.append((start_ind, area))

areas = [areas[i][1] for i in range(len(areas))]
print(sum(areas))
print(str(len(areas)) + " " + " ".join(map(str,areas)) if not len(areas) == 0  else "0")

Submission status: Accepted

Solution code:
s = input()
st1=[]
st2=[]
st3=[]
n=len(s)
lv = 0
for i in range(n):
	c=s[i]
	if c=='\\':
		lv-=1
		st1.append(i)
	elif c=='/':
		lv+=1
		if len(st1) > 0:
			a = i - st1.pop()
			if len(st2)==0 or st2[len(st2)-1]>=lv:
				st3.append(a)
			else:
				t=0	
				while len(st2)>0 and st2[len(st2)-1]<lv:
					st2.pop()
					t+=st3.pop()
				st3.append(a+t)		
			st2.append(lv)
		else:
			if len(st2) > 0:
				st2.pop()
				st2.append(lv)
				
st=''
total=0
n = len(st3)
st+=str(n)
for i in range(n):
	st+=' '+str(st3[i])
	total+=(st3[i])
print(total)
print(st)

Submission status: Accepted

Solution code:
s = input()
st1=[]
st2=[]
st3=[]
n=len(s)
lv = 0
for i in range(n):
	c=s[i]
	if c=='\\':
		lv-=1
		st1.append(i)
	elif c=='/':
		lv+=1
		if len(st1) > 0:
			a = i - st1.pop()
			t=0	
			while len(st2)>0 and st2[-1]<lv:
				st2.pop()
				t+=st3.pop()
			st3.append(a+t)		
			st2.append(lv)
		else:
			if len(st2) > 0:
				st2.pop()
				st2.append(lv)
				
st=''
total=0
n = len(st3)
st+=str(n)
for i in range(n):
	st+=' '+str(st3[i])
	total+=(st3[i])
print(total)
print(st)

Submission status: Accepted

Solution code:
s = input()
st1=[]
st2=[]
st3=[]
n=len(s)
lv = 0
for i in range(n):
	c=s[i]
	if c=='\\':
		lv-=1
		st1.append(i)
	elif c=='/':
		lv+=1
		if len(st1) > 0:
			a = i - st1.pop()
			t=0	
			while len(st2)>0 and st2[-1]<lv:
				st2.pop()
				t+=st3.pop()
			st3.append(a+t)		
			st2.append(lv)
		elif len(st2) > 0:
				st2.pop()
				st2.append(lv)
				
st=''
total=0
n = len(st3)
st+=str(n)
for i in range(n):
	st+=' '+str(st3[i])
	total+=(st3[i])
print(total)
print(st)

Submission status: Accepted

Solution code:
s = input()
st1=[]
st2=[]
st3=[]
n=len(s)
lv = 0
total=0
for i in range(n):
	c=s[i]
	if c=='\\':
		lv-=1
		st1.append(i)
	elif c=='/':
		lv+=1
		if len(st1) > 0:
			a = i - st1.pop()
			total+=a
			tmp=0	
			while len(st2)>0 and st2[-1]<lv:
				st2.pop()
				tmp+=st3.pop()
			st3.append(a+tmp)		
			st2.append(lv)
		elif len(st2) > 0:
			st2.pop()
			st2.append(lv)
		
print(total)
n = len(st3)
print(n,end='')
for i in range(n):
	print(' '+str(st3[i]),end='')
print()

Submission status: Accepted

Solution code:
s = input()
st1=[]
st2=[]
st3=[]
total=0
for i in range(len(s)):
	c=s[i]
	if c=='\\':
		st1.append(i)
	elif c=='/':
		if len(st1) > 0:
			j = st1.pop()
			a = i - j
			total+=a
			tmp=0
			while len(st2)>0 and st2[-1]>j:
				st2.pop()
				tmp+=st3.pop()
			st3.append(a+tmp)
			st2.append(j)
			
print(total)
n = len(st3)
print(n,end='')
for i in range(n):
	print(' '+str(st3[i]),end='')
print()

Submission status: Accepted

Solution code:
s = input()
st1=[]
st2=[]
st3=[]
total=0
for i in range(len(s)):
	c=s[i]
	if c=='\\':
		st1.append(i)
	elif c=='/':
		if len(st1) > 0:
			j = st1.pop()
			a = i - j
			total+=a
			tmp=0
			while len(st2)>0 and st2[-1][0]>j:
				tmp+=st2[-1][1]
				st2.pop()
			st2.append((j,a+tmp))
			
print(total)
n = len(st2)
print(n,end='')
for i in range(n):
	print(' '+str(st2[i][1]),end='')
print()

Submission status: Accepted

Solution code:
def main():
    line = input()
    deepen_x = []
    cur_x = 0
    ponds = []      # [(水たまりの最初の位置, 水量)]
    while len(line) > 0:
        #print(cur_x, ponds, deepen_x)
        tmp_char = line[0]
        if tmp_char == '\\':
            deepen_x.append(cur_x)
        elif tmp_char == '/' and len(deepen_x) != 0:
            pre_x = deepen_x.pop()
            volume = cur_x - pre_x
            if len(ponds) == 0:
                ponds.append([pre_x, volume])
            else:
                if pre_x < ponds[-1][0]:
                    # 前の水たまりと結合する
                    a = list(filter(lambda x: x[0] > pre_x, ponds))
                    pond = 0
                    for item in a:
                        pond += item[1]
                    [ponds.pop() for x in range(len(a))]
                    ponds.append([pre_x, pond + volume])
                else:
                    # 新しい水たまりを作成
                    ponds.append([pre_x, volume])
        cur_x += 1
        line = line[1:]

    print(sum([x[1] for x in ponds]))
    if len(ponds) == 0:
        print('0')
    else:
        print("{} ".format(len(ponds)) + " ".join([str(x[1]) for x in ponds]))

    return


main()

Submission status: Accepted

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

count = 0
backslash_index = []
area_pond = []
pending_area=[]
for index,symbol in enumerate(input()):
	if symbol == "\\":
		backslash_index += [index]
	elif symbol == '/' and backslash_index:
		last_bs_index = backslash_index.pop()
		diff = index - last_bs_index 
		count += diff 
		while area_pond and area_pond[-1] > last_bs_index:
			diff += pending_area.pop()
			area_pond.pop()

		area_pond += [last_bs_index]
		pending_area += [diff]

print(count)
print(len(area_pond),*(pending_area))
#print(len(area_pond), ' '.join(map(str, pending_area)))

Submission status: Accepted

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

count = 0
backslash_index = []
area_pond = []
pending_area=[]
for index,symbol in enumerate(input()):
	if symbol == "\\":
		backslash_index += [index]
	elif symbol == '/' and backslash_index:
		last_bs_index = backslash_index.pop()
		diff = index - last_bs_index 
		count += diff 
		while area_pond and area_pond[-1] > last_bs_index:
			diff += pending_area.pop()
			area_pond.pop()

		area_pond += [last_bs_index]
		pending_area += [diff]

print(count)
print(len(area_pond),*(pending_area))

Submission status: Accepted

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

count = 0
backslash_index = []
area_pond = []
pending_area=[]
for index,symbol in enumerate(input()):
	if symbol == "\\":
		backslash_index += [index]
	elif symbol == '/' and backslash_index:
		last_bs_index = backslash_index.pop()
		diff = index - last_bs_index 
		count += diff 
		while area_pond and area_pond[-1] > last_bs_index:
			diff += pending_area.pop()
			area_pond.pop()

		area_pond += [last_bs_index]
		pending_area += [diff]

print(count)
print(len(area_pond),*(pending_area))

Submission status: Accepted

Solution code:
lines = input()
stack_1 = []
stack_2 = []

area = 0
for i, line in enumerate(lines):
    if line == '\\':
        stack_1.append(i)
    elif line == '_':
        pass
    elif line == '/':
        if stack_1 == []:
            continue
        last_index = stack_1.pop()
        this_area = i - last_index
        area += this_area

        if stack_2 == []:
            stack_2.append((last_index, this_area))
            continue

        block_area = this_area
        while True:
            if stack_2 == []:
                break
            stack_2_index, stack_2_area = stack_2.pop()
            if stack_2_index < last_index:
                stack_2.append((stack_2_index, stack_2_area))
                break
            else:
                block_area += stack_2_area
        stack_2.append((last_index, block_area))

print(area)
kazu = len(stack_2)
kaku_menseki = [stack_2[i][1] for i in range(len(stack_2))]
kaku_menseki_out = ' '.join(map(str, kaku_menseki))
if kazu > 0:
    print(f'{kazu} {kaku_menseki_out}')
else:
    print(f'{kazu}')

Submission status: Accepted

Solution code:
"""
アルゴリズムとデータ構造 P.116
をPythonで書いた
"""

s = input()
stack1 = list()
stack2 = list()
sm = 0

for i, c in enumerate(s):
    if c == '\\':
        stack1.append(i)
        continue

    if c == '/' and len(stack1) > 0:
        j = stack1.pop()
        sm += i - j
        a = i - j
        while len(stack2) > 0 and stack2[-1][0] > j:
            a += stack2.pop()[1]
        stack2.append((j, a))

print(sm)
ans = list()
ans.append(len(stack2))
for _, a in stack2:
    ans.append(a)
print(" ".join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
lakes = []  # [(左岸位置, 断面積)]
lefts = []  # lefts[i]: まだ対になっていない上から i 番目の左岸位置
for i, c in enumerate(input()):
	if c == '\\':
		lefts.append(i)
	elif c == '/':
		if lefts:
			left = lefts.pop()
			area = i - left
			while lakes:
				sub_left, sub_area = lakes[-1]
				if left < sub_left:
					area += sub_area
					lakes.pop()
				else:
					break
			lakes.append((left, area))

L = [lake[1] for lake in lakes]
print(sum(L))
print(len(L), *L)

Submission status: Accepted

Solution code:
A = input()
st = [(0, 0, -1)]
cur = 0; ma = 0
for i, a in enumerate(A):
    if a == '/':
        cur += 1
        s = 0
        while st and st[-1][0] == cur-1 and cur <= ma:
            lev, su, j = st.pop()
            s += su
        if st and st[-1][0] == cur:
            s += i - st[-1][2] - 1
        ma = max(ma, cur)
        st.append((cur, s, i))
    elif a == '\\':
        cur -= 1
        st.append((cur, 0, i))
    elif a == '_':
        st.append((cur, 0, i))
ans = []
for lev, su, j in st:
    if su > 0:
        ans.append(su)
print(sum(ans))
print(len(ans), *ans)

Submission status: Accepted

Solution code:
diagram = input()

water_all = 0
water = 0
ip = 0
stack1 = []
stack2 = []

for i, symbol in enumerate(diagram):
    if symbol == '\\': # 一つのバックスラッシュはこう書くらしい
        stack1.append(i)
    elif symbol == '/':
        if stack1 != []:
            ip = stack1.pop()
            water = i - ip
            water_all += water
            
            if stack2 != []:
                while stack2[-1][0] > ip:
                    i2, water2 = stack2.pop()
                    water += water2
                    if stack2 == []:
                        break
                stack2.append([ip, water])
            else:
                stack2.append([ip, water])

s = str(len(stack2))
waters = [str(i[1]) for i in stack2]
if len(waters)!=0:
    s += ' ' + ' '.join(waters)

print(water_all)
print(s)

Submission status: Accepted

Solution code:
l={}
s=[]
h=[0]
n=d=m=0
for c in raw_input():
    if c=="\\":
        l[d]=n
        d-=1
    elif c=="/":
        d+=1
        if d in l:
            while len(s) and s[-1][1]>l[d]: s.pop()
            s.append([l[d],n])
    n+=1
    h.append(d)

a=[sum([h[i]-k for k in h[i:j+1]]) for i,j in s]
print sum(a)
print " ".join(map(str,[len(a)]+a))

Submission status: Accepted

Solution code:
def func(c):
    global cnt
    cnt += {'_':0, '/':1, '\\':-1}[c]
    return cnt

cnt = 0
g = [[0, False]] + [[func(c), False] for c in input()]

gmax = g[0][0]
for i in range(1, len(g)):
    if g[i - 1][0] < g[i][0] <= gmax :
        g[i][1] = True
    gmax = max(gmax, g[i][0])

puddles = []
volume = 0
saface_level = None

for i in range(len(g) - 1, -1, -1):
    if saface_level != None:
        volume += saface_level  - g[i][0]
        if saface_level == g[i][0]:
            puddles += [volume]
            saface_level = None
            volume = 0
    if saface_level == None and g[i][1]:
        saface_level = g[i][0] 

puddles = puddles[::-1]
print(sum(puddles))
print(len(puddles), *puddles)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_D
# Areas on the Cross-Section Diagram
# Result:
import sys

class Stack(object):
    def __init__(self):
        self.store = []

    def push(self, val):
        self.store.append(val)

    def pop(self):
        if self.is_empty():
            return None
        return self.store.pop()

    def top(self):
        if self.is_empty():
            return None
        return self.store[len(self.store) - 1]

    def is_empty(self):
        if len(self.store) == 0:
            return True
        else:
            return False

    def to_list(self):
        return list(self.store)


### main
pools = []
s1 = Stack()
s2 = Stack()

line = sys.stdin.readline().rstrip()
area_sum = 0
idx = 0
for c in line:
    if c == '\\':
        s1.push(idx)
    elif c == '/':
        if not s1.is_empty():
            bs_idx = s1.pop()
            this_area_sum = idx - bs_idx
            area_sum += this_area_sum
            while (not s2.is_empty()) and (s2.top()[0] > bs_idx):
                this_area_sum += s2.pop()[1]
            s2.push((bs_idx, this_area_sum))
    else:
        pass
    idx += 1

print area_sum
s2_list = s2.to_list()
str = '%d' % (len(s2_list))
for e in s2.to_list():
    str += ' %d' % (e[1])
print str

Submission status: Accepted

Solution code:
S = raw_input()
S1, S2 = [], []

ans = pool = 0
for i in xrange(len(S)):
    if S[i] == "/" and len(S1) > 0:
        j = S1.pop()
        ans += i - j
        a = i - j
        while (len(S2) > 0 and S2[-1][0] > j):
            a += S2.pop()[1]
        S2.append([j, a])
    if S[i] == "\\":
        S1.append(i)
print ans
if len(S2) > 0:
    print len(S2), " ".join(map(str, [a for j, a in S2]))
else:
    print 0