3695 - iziStack

Enunt

Se dă o stivă vidă. Elementele stivei sunt numerotate incepand cu 1 de la bază înspre vârf. Avem de procesat T comenzi de tipurile:

• 0 x – elementul x se va adăuga în vârful stivei
• 1 x y add – tuturor elementelor din intervalul x y le va fi adăugată valoarea add
• 2 – eliminarea elementului din vârf

Cerinţa

Afisați dupa fiecare operație elementul din vârful stivei. Se garantează: 1. că nu se va efectua operația de tip 2 dacă nu există cel puțin două elemente în stivă; 2. că prima operatie va fi de tipul 0

Date de intrare

Fișierul de intrare izi.in conține pe prima linie un număr natural T, iar pe următoarele T linii operațiile efectuate asupra stivei.

Date de ieșire

Fișierul de ieșire izi.out va conține T linii, reprezentând elementele din vârful stivei dupa fiecare operație.

Restricţii şi precizări

• 1 ≤ T ≤ 1.000.000
• -1000 ≤ add ≤ 1000
• Pentru operațiile de tip 1, -1000 ≤ x ≤ 1000, iar pentru operatiile de tip 2 numărul elementelor aflate în stivă este mai mare ca y
• Pentru 36 puncte: 1 ≤ T ≤ 1000
• Pentru alte 33 puncte: Toate operatiile de tip 2 se vor afla la finalul fișierului de intrare

Exemplu

izi.in

7
0 1
1 1 1 2
0 2
1 1 2 3
2
0 4
2

izi.out

1
3
2
5
6
4
6

Rezolvare

<syntaxhighlight lang="python" line> class Stack:

   def __init__(self):
       self.stack = []

   def push(self, x):
       self.stack.append(x)

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

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

   def is_empty(self):
       return len(self.stack) == 0

def process_operations(T, operations):

   stack = Stack()
   for op in operations:
       if op[0] == 0:
           stack.push(op[1])
       elif op[0] == 1:
           x, y, add = op[1], op[2], op[3]
           for i in range(x - 1, y):
               stack.stack[i] += add
       elif op[0] == 2:
           stack.pop()
       if not stack.is_empty():
           print(stack.top())

def main():

   T = int(input())
   operations = []
   for _ in range(T):
       operation = list(map(int, input().split()))
       operations.append(operation)
   process_operations(T, operations)

if __name__ == "__main__":

   main()

</syntaxhighlight>