Un jeu à la Tetris™ II

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

TIME AND MEMORY LIMITS (Python)

  • Time: 1s on a 1GHz machine.
  • Memory: 64,000 KB.

CONSTRAINTS

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.

INPUT

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: https://www.france-ioi.org. Created by : Arthur Charguéraud, d'après une idée de Guillaume Ryder.