## CCC '17 S5 - RMT

View as PDF

Points: 20 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem type
##### Canadian Computing Competition: 2017 Stage 1, Senior #5

The Rail Metro Transit (RMT) operates a very unusual subway system. There are subway stations numbered from to . There are subway lines numbered from to , with each station belonging to exactly one line and at least one station per line. The subway lines are circular. That is, if a station is numbered , the next station after is the station on the same line with the next largest number, unless is the greatest number of a station in the line, in which case the next station after is the station on the same line with the least number.

RMT is conducting a load test of their system using volunteer passengers to ride the subway trains. The test begins with one subway train in each station and for every , there are passengers in the train at station . The volunteers do not leave their assigned trains throughout the entire duration of the load test.

Throughout the test, RMT will perform actions. Each of the actions is one of two types: either they will survey the total number of passengers in the trains at the stations numbered from to ; or they will operate all the trains on some line . When a train on line is operated, it goes to the next station in that line.

You are RMT's biggest fan, so you have generously volunteered to keep track of RMT's actions and report the answers to their surveys.

#### Input Specification

The first line will contain three space-separated integers , , and . The second line will contain the subway line numbers that each station from to belongs to: . The third line will contain integers representing the initial number of passengers at each station from to .

The next lines will each have one of the following forms:

• , which represents a survey .
• , which represents RMT operating line .

For 2 of the 15 available marks, and .
For an additional 2 of the 15 available marks, .
For an additional 3 of the 15 available marks, .
For an additional 3 of the 15 available marks, there will be no more than trains on any single line.

#### Output Specification

For every survey, output the answer to the survey on a separate line.

#### Sample Input 1

5 2 5
1 2 1 2 2
1 2 3 4 5
1 1 5
2 1
1 3 5
2 2
1 1 3

#### Sample Output 1

15
10
9

#### Explanation for Sample Output 1

The subway system is illustrated below, with the stations numbered from 1 to 5 and the lines connecting stations marked as either being line 1 or line 2:

Initially, the number of passengers at each station is .
The answer to the first survey is .
After line is operated, the number of passengers at each station is .
The answer to the second survey is .
After line is operated, the number of passengers at each station is .
The answer to the third survey is .

#### Sample Input 2

3 1 7
1 1 1
114 101 109
1 1 1
2 1
1 1 1
2 1
1 1 1
2 1
1 1 1

#### Sample Output 2

114
109
101
114

#### Explanation for Sample Output 2

The subway system is illustrated below, with the stations numbered from 1 to 3 and the lines connecting stations marked as all being line 1:

Just before the first survey, the number of passengers at each station is .
Just before the second survey, the number of passengers at each station is .
Just before the third survey, the number of passengers at each station is .
Just before the fourth survey, the number of passengers at each station is .

• commented on Jan. 11, 2018, 1:12 p.m.

-Spoilers-

I have O(n) query and O(1) update, and I'm hitting TLE. Batch 2's constraints give an obvious solution to that set by saving line totals by ranges, but I don't see how that would apply to the later Batches when stations aren't continuous.

Would any/all of the submitted answers finish in time for N=M=Q=150000 of only 1 1 150000? Am I missing a breakthrough or am I just not storing enough info to later reuse?

I can think of small casing things that could improve times in special cases (keep a line's passengers + min and max station #, if min + max are in range just add the line's passengers; but flagging that you added each station would take as long as the lookup anyways, so you would need to do this for every line or no lines; but then you have lines that aren't fully contained in a range where you have to subtract... etc. etc.)

I can't find the solutions anywhere else and this is bugging me, so any help is much appreciated.

• commented on Sept. 21, 2017, 8:44 a.m. edit 3

nvm

• commented on Sept. 21, 2017, 9:34 a.m. edit 3

Well since and , updates taking time would result in at least operations per second in the worst case, and would almost certainly TLE.

• commented on March 6, 2017, 7:26 p.m.

Wait... there are at least 400 test cases... If all of them hits 7.0s exactly, that's like 47 minutes....

• commented on July 8, 2019, 9:50 p.m. edited

On the website, there are 40 test cases, but here there are like 475. Are the other ones unofficial?

• commented on March 6, 2017, 7:40 p.m.

And that there is why we have 4 judges.

• commented on March 14, 2017, 9:35 p.m.

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

• commented on March 14, 2017, 10:09 p.m.

Submissions only run on one judge at a time.