Un jeu à la Tetris™ II

Ce sujet est identique à Un jeu à la Tetris™, à la seule différence que les contraintes sont bien plus grandes.

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 64 000 ko.

Contraintes

Le cadre du jeu contiendra toujours 100000 colonnes, numérotées de 0 à 99999 inclus. Il n'y a a priori pas de limite au nombre de lignes.

Entrée

L'entrée est formée de :

  • Sur la première ligne, un entier N : le nombre de bâtons qui vont tomber, avec 1 <= N <= 10000.
  • Chacune des N lignes suivantes contient la description d'un bâton.
    Un bâton est décrit par une lettre puis deux entiers, séparés par des espaces :
    • une lettre qui donne l'orientation du bâton : 'H' pour horizontale, 'V' pour verticale.
    • un entier qui donne la longueur Li du bâton, avec 1 <= Li <= 100000.
    • un entier qui donne la colonne Ci du bord le plus à gauche du bâton, avec 0 <= Ci <= 99999.

Source : http://www.france-ioi.org/ Créé par : Arthur Charguéraud, d'après une idée de Guillaume Ryder.