## GFSSOC '14 Winter S4 - Stalactites

View as PDF

Points: 17 (partial)
Time limit: 2.5s
Memory limit: 256M

Authors:
Problem type

It is now Griffy's turn to hide! Unfortunately, he has strayed a bit too far and has found himself trapped in an ice cave (what are the odds?). Griffy was getting very lonely, so he decided to make friends with all the stalactites in there! The cave is by coincidence a perfect cube . The cube can be thought of as a series of coordinates, where the coordinates are in the range to . At each set of integer coordinates, one stalactite can be found. As an icebreaker, Griffy decides to count the sum of the lengths of all the stalactites inside a rectangular volume. The game gets harder though, as each stalactite can change in length. Given the changing conditions, help Griffy master this game. You can assume that no stalactite changes length while Griffy is counting the sum. Stalactites all start with the same length of . You can also assume that the length of a stalactite at any point will always be a non-negative integer less than or equal to .

Note: At least 30% of the test cases will have all the change length commands coming before the sum commands.

#### Input Specification

First line: , the size of the cubic cave.

Second line: , the number of events (changing stalactite length, or sum of prism).

The next lines are each in the form of:

• The stalactite in the coordinate of has changed to a length of .

• Find the sum of the stalactites in the rectangular prism bounded by the corners and .

#### Output Specification

One line, the sum of all of the sum queries.

#### Sample Input

2
5
C 1 1 2 5
C 1 2 2 5
C 2 1 2 5
S 1 1 1 2 2 2
S 1 1 2 1 1 2

#### Sample Output

20

#### Explanation for Sample Output

The answer to the first sum query is , and the answer to the second one is .

• commented on Dec. 8, 2017, 1:26 p.m.

It's not that strict for java ... Just watch some details ^^

• commented on May 28, 2016, 8:30 p.m. edited

Submissions with correct algorithm in Java can't pass in time (tested by resubmitting jeffreyxiao's 100/100 submission several times).

Edit: It passes now.

• commented on March 11, 2015, 9:46 p.m.

Is it even possible to do this with languages like java without exceeding the 256 MB mem limit?

• commented on March 11, 2015, 10:21 p.m.

Yes; an unoptimized solution translated from C++ passes just in time (http://www.dmoj.ca/submission/67640).

270mb is used in the max case, but while we display the total VM memory, heap space is used to determine MLE (and the heap is smaller, just slightly, than 256mb).

You'll want to use BufferedReader or similar for input: Scanner passes through sheer luck in 4.998 seconds for max case.

• commented on March 12, 2015, 9:05 a.m.

If it is THAT close, then why not just increase the memory limit by a little bit?

• commented on March 12, 2015, 1:55 p.m.

Why? It's perfectly passable in C++. If you can't pass in Java, sucks to be you.

• commented on March 12, 2015, 5:06 p.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on March 26, 2020, 12:30 a.m.

other languages exist outside the competitive programming atmosphere

• commented on March 11, 2015, 10:27 p.m.

k thanks for clearing up.