time limit per test: 1.25 sec. memory limit per test: 65536 KB
input: standard output: standard
Vasya likes to play unusual games very much. One of these games is building towers. Unfortunately he is very tired today and instead of building towers himself, he wants his favorite robot to build towers for him. So, this time, Vasya will be laying on his couch sending commands to his robot. The process of constructing towers is very easy. Imagine that you have a number of cells in a row. Cells are numbered from 1 to 10^6 and initially are empty. Robot can move to specified cell and put some number of cubes on it. If there are some cubes already on the cell, he will put new cubes on the top of the existing ones. For two integers i and j (i <= j) the cubes on cells i..j are called 'tower', if on any cell with number k, i <= k <= j, there is a positive number of cubes, and there are no cubes on cell i-1 (or i is the leftmost cell in the row) and cell j+1 (or j is the rightmost cell in the row). Length of the tower is j-i+1 - the number of columns in it. Within each tower the columns can be numbered from 1 to its length from the left to the right, so instead of giving robot a cell number, Vasya can give robot a tower number and column number within the tower. As you can guess, your task is to write a robot that will process commands from Vasya. Robot must be able to build towers and respond to simple questions (see below). Here is the list of available commands:
put <x> <c> - put c cubes on cell x
tput <t> <x> <c> - put c cubes on column x in tower with number t (towers are numbered from left to the right)
towers - print total number of towers built
cubes <t> - print the number of cubes in the tower t
length <t> - print the length of the tower t
tcubes <t> <x> - print the number of cubes in column x of the tower t
The first line of input file contains a number of commands N (1 <= N <= 10^6). Each of the following N lines contains a command. It's guaranteed that all input commands are correct (cell number c is always in range 1..10^6, tower t always exists, column x inside tower always exists and its corresponding cell number is also in range 1..10^6). You can assume that no cell will have more than 2^31-1 cubes on it.
For the commands that require printing, output exactly one line according to the format of sample output file below. Please, do not follow English grammar rules and print '1 towers' instead of '1 tower'. The same applies for printing '1 cubes' and '1th', '2th' and '3th'.
22 towers put 2 5 put 1 6 put 3 6 put 3 3 towers length 1 put 6 3 put 5 4 length 2 tcubes 2 1 tcubes 2 2 towers cubes 1 cubes 2 put 4 3 towers cubes 1 tput 1 6 50 cubes 1 tcubes 1 6 length 1
0 towers 1 towers length of 1th tower is 3 length of 2th tower is 2 4 cubes in 1th column of 2th tower 3 cubes in 2th column of 2th tower 2 towers 20 cubes in 1th tower 7 cubes in 2th tower 1 towers 30 cubes in 1th tower 80 cubes in 1th tower 53 cubes in 6th column of 1th tower length of 1th tower is 6
This problem has huge tests. Some read/write routines work very slow in several compilers (especially, C/C++: try to use getc() putc() functions to avoid IO troubles).
Roman V. Alekseenkov
Saratov SU Contest: Golden Fall 2004
October 2, 2004
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov