TSOC '15 Contest 2 #6 - All-Out War!

View as PDF
Submit solution
Points: 5 (partial)
Time limit: 0.6s
Java 8 1.0s
PyPy 2 1.4s
PyPy 3 1.4s
Memory limit: 64M
Java 8 30M
PyPy 2 30M
PyPy 3 30M
Authors:
bobhob314, kobortor
Problem type

Thanks to Max's invaluable leadership, a sizable portion of the ex-convicts are still alive and mentally stable! But before they can return home to their families, Joey orders them to exterminate the bebiliths, even if it costs them their lives!

The bebiliths pour out of the cave, aligned in N (1 \le N \le 30\,000) columns. The columns are aligned such that one bebilith from each column is visible to the ex-convicts. There are R_i (0 \le R_i \le 10^9) bebiliths in the i^{th} column. Joey commands Q (1 \le Q \le 30\,000) strategic offenses, during which the ex-convicts eliminate c (1 \le c \le 10^9) bebiliths from each column for all the columns in [a, b] (1 \le a \le b \le N).

After every strategic offense from the ex-convicts, Joey wants to evaluate the enemy's condition by finding the strength of the weakest column of bebiliths for all the columns in [a, b], and then the same for all the columns in [1, N]. Help Joey lead the ex-convicts to victory!

This problem can be solved with a brute force solution. As a result, the point value has been lowered to 5 points. If you want to strengthen the data, please send a message to the #problems-in-problems channel on slack.

Input Specification

The first line will contain N and Q, separated by a single space.
The second line will contain N integers, with each containing the value R_i.
The next Q lines will each contain three space-separated integers a b c.

Output Specification

For every strategic offense, print out the number of bebiliths in the weakest column in the range of columns [a, b], and the same for the range of columns [1, N], separated by a single space.

Sample Input

3 3
4 4 4
1 1 3
2 3 2
1 3 7

Sample Output

1 1
2 1
0 0

Language Limits

  • PyPy2/PyPy3: 3s, 30MB
  • Java7/Java8: 2s, 30MB

Visual Aid

Comments


  • 11
    bobhob314  commented on Dec. 21, 2015, 5:15 p.m. ← edit 5

    It's kind of funny because I'm listed as an author, but do we have to output the lowest-indexed column if there is a tie?

    Also why is the last test case have 0 0 when the columns are 1-indexed? Is 0 to be outputted if all columns are 0?

    Edit: This problem was written poorly (mostly by me). I don't want to start something for the umpteenth time, so I'll wait for Fatal's approval before I change the question, but basically you are to output the minimum value, not the minimum-value column. Bless you.

    Edit 2: Also, it is entirely possible that there is an issue in the test data.

    Edit 3: Nah it's just weak. Issue closed.


  • 7
    nullptr  commented on April 20, 2015, 4:53 p.m.

    -


    • 6
      Xyene  commented on April 20, 2015, 5:30 p.m.

      The issue is resolved and all submissions are being rejudged.


      • 1
        bobhob314  commented on April 20, 2015, 5:43 p.m. ← edit 2

        Hi Timothy,

        Please set me as an administrator.

        I had no prior knowledge that edits announcing changes to be made for a problem during a contest was against an internal rule.

        Regards,

        Max.

        Edit

        • I only decided to participate in this contest to comment this. Please don't calculate rating for me using this contest.

        • How is the issue not resolved?


    • 0
      moladan123  commented on April 20, 2015, 5:11 p.m.

      I'l let thispass once guys, but only because I got 25 FREE POINTS.


    • 1
      awaykened  commented on April 19, 2015, 5:31 p.m.

      lol also tudor can you restrict my powers so I can't see contest problems


      • 0
        bobhob314  commented on April 19, 2015, 6:07 p.m.

        Weiwei, could you try solving this problem and emailing me at [email protected] the code??

        The contest is tomorrow so it's an emergency

        Thanks


      • 1
        bobhob314  commented on April 19, 2015, 5:47 p.m. ← edit 3

        xD <3 Weiwei

        i <3 u