GFSSOC '14 Winter S4 - Stalactites - DMOJ: Modern Online Judge

GFSSOC '14 Winter S4 - Stalactites

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 $(N \times N \times N)$ $(N \times N \times N)$ . The cube can be thought of as a series of $(X, Y, Z)$ $(X, Y, Z)$ coordinates, where the coordinates are in the range $1$ $1$ to $N$ $N$ . 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 $0$ $0$ . 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 $1\,000\,000$ $1 000 000$ .

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

Input Specification

First line: $N$ $N$ $(2 \le N \le 250)$ $(2 \leq N \leq 250)$ , the size of the cubic cave.

Second line: $Q$ $Q$ $(1 \le Q \le 500\,000)$ $(1 \leq Q \leq 500 000)$ , the number of events (changing stalactite length, or sum of prism).

The next $Q$ $Q$ lines are each in the form of:

$\mathrm{C}\ X\ Y\ Z\ L$ $C X Y Z L$

The stalactite in the coordinate of $(X, Y, Z)$ $(X, Y, Z)$ has changed to a length of $L$ $L$ .
$\mathrm{S}\ X_1\ Y_1\ Z_1\ X_2\ Y_2\ Z_2$ $S X_{1} Y_{1} Z_{1} X_{2} Y_{2} Z_{2}$

Find the sum of the stalactites in the rectangular prism bounded by the corners $(X_1, Y_1, Z_1)$ $(X_{1}, Y_{1}, Z_{1})$ and $(X_2, Y_2, Z_2)$ $(X_{2}, Y_{2}, Z_{2})$ $(X_1 \le X_2; Y_1 \le Y_2; Z_1 \le Z_2)$ $(X_{1} \leq X_{2}; Y_{1} \leq Y_{2}; Z_{1} \leq Z_{2})$ .

Output Specification

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

Sample Input

Copy

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

Copy

Explanation for Sample Output

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

$15+5 = 20$ $15 + 5 = 20$

Comments

3

yuyoung1527 commented on Dec. 8, 2017, 6:26 p.m.

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

7

r3mark commented on May 29, 2016, 12:30 a.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.

2

kobortor commented on March 12, 2015, 1:46 a.m.

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

5

Xyene commented on March 12, 2015, 2:21 a.m. ← edited →

Yes; an unoptimized solution translated from C++ passes just in time (https://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.

0

moladan123 commented on March 12, 2015, 1:05 p.m.

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

7

FatalEagle commented on March 12, 2015, 5:55 p.m.

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

-33

bobhob314 commented on March 12, 2015, 9:06 p.m.

Amen. All you people that don't know C or C++, lol. Good try. Be better at programming and learn some ACTUAL languages!

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

10

pblpbl commented on March 26, 2020, 4:30 a.m.

other languages exist outside the competitive programming atmosphere

5

kobortor commented on March 12, 2015, 2:27 a.m.

k thanks for clearing up.