GFSSOC '14 Winter S4 - Stalactites

View as PDF

Submit solution

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

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

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 (2 \le N \le 250), the size of the cubic cave.

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

The next Q lines are each in the form of:

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

    The stalactite in the coordinate of (X, Y, Z) has changed to a length of L.

  • \mathrm{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) and (X_2, Y_2, Z_2) (X_1 \le X_2; Y_1 \le Y_2; Z_1 \le Z_2).

Output Specification

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

Sample Input

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


Explanation for Sample Output

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

15+5 = 20


  • 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 (

      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.

            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.