The city of Brisbane has been taken over by large mutated wombats, and you must lead the people to safety.
The roads in Brisbane are laid out in a large grid. There are horizontal roads that run easttowest, numbered in order from north to south, and vertical roads that run northtosouth, numbered in order from west to east, as shown in the picture below.
The wombats have invaded from the north, and the people are escaping to the south. People can run along horizontal roads in either direction, but on vertical roads they will only run towards the south, towards safety.
The intersection of horizontal road with vertical road is denoted . Each segment of road between two intersections contains some number of wombats, and these numbers may change over time. Your task is to guide each person from some given intersection in the north (on horizontal road ) to some given intersection in the south (on horizontal road ), taking them on a route that passes as few wombats as possible.
To begin, you will be given the size of the grid and the number of wombats on each road segment. Following this you will be given a series of events, each of which is either:
 a change, which alters the number of wombats on some road segment; or
 an escape, where some person arrives at a given intersection on horizontal road , and you must find a route to a given intersection on horizontal road that passes the fewest possible wombats.
You must handle these events by implementing the routines init()
, changeH()
, changeV()
and escape()
, as described below.
Examples
The picture above shows an initial map with horizontal roads and vertical roads, with the number of wombats marked on each segment. Consider the following series of events:
 A person arrives at intersection and wishes to escape to intersection . The smallest number of wombats she can pass is , as indicated by a dashed line.
 Another person arrives at intersection and wishes to escape to intersection . The smallest number of wombats he can pass is , again indicated by a dashed line.
 Two change events occur: the number of wombats on the top segment of vertical road changes to , and the number of wombats on the middle segment of horizontal road changes to . See the circled numbers in the picture below.
 A third person arrives at intersection and wishes to escape to intersection . Now the smallest number of wombats she can pass is , as indicated by the new dashed line.
Implementation
You should submit a file implementing the procedures init()
, changeH()
and changeV()
and the function escape()
, as follows:
Grader Procedure: init()
C/C++
void init(int R, int C, int H[5000][200], int V[5000][200]);
Pascal
type wombatsArrayType = array[0..4999, 0..199] of LongInt;
procedure init(R, C : LongInt; var H, V : wombatsArrayType);
Description
This procedure gives you the initial layout of the map, and allows you to initialise any global variables and data structures. It will be called only once, before any calls to
changeH()
,changeV()
orescape()
.
Parameters
R
: The number of horizontal roads.C
: The number of vertical roads.H
: A twodimensional array of size , where gives the number of wombats on the segment of horizontal road between intersections and .V
: A twodimensional array of size , where gives the number of wombats on the segment of vertical road between intersections and .
Grader Procedure: changeH()
C/C++
void changeH(int P, int Q, int W);
Pascal
procedure changeH(P, Q, W: LongInt);
Description
This procedure will be called when the number of wombats changes on the horizontal road segment between intersections and .
Parameters
P
: Indicates which horizontal road is affected .Q
: Indicates between which two vertical roads the segment lies .W
: The new number of wombats on this road segment .
Grader Procedure: changeV()
C/C++
void changeV(int P, int Q, int W);
Pascal
procedure changeV(P, Q, W: LongInt);
Description
This procedure will be called when the number of wombats changes on the vertical road segment between intersections and .
Parameters
P
: Indicates between which two horizontal roads the segment lies .Q
: Indicates which vertical road is affected .W
: The new number of wombats on this road segment .
Grader Function: escape()
C/C++
int escape(int V1, int V2);
Pascal
function escape(V1, V2 : LongInt) : LongInt;
Description
This function should calculate the fewest possible wombats a person must pass when travelling from intersection to .
Parameters
V1
: Indicates where the person begins on horizontal row .V2
: Indicates where the person ends on horizontal row . Returns: The smallest number of wombats the person must pass.
Sample Session
The following session describes the sample above:
Function Call  Returns 

init(3, 4, [[0,2,5], [7,1,1], [0,4,0]], [[0,0,0,2], [0,3,4,7]])  
escape(2,1)  2 
escape(3,3)  7 
changeV(0,0,5)  
changeH(1,1,6)  
escape(2,1)  5 
Constraints
 Time Limit: 20 seconds
 Memory Limit: 256 MiB
 At most changes (calls to either
changeH()
orchangeV
)  At most calls to
escape()
 At most wombats on any segment at any time
Subtasks
Subtask  Points  Additional Input Constraints 

1  9  
2  12 
, and there will be no calls to changeH() or changeV()

3  16 
, and there will be at most calls to escape()

4  18  
5  21  
6  24  (None) 
Comments
Note that the judge frees / destroys the arrays given in
init
after calling it, so you can't use it afterwards.help, why is it wrong? runs well on muy complier and on wcipeg, why is dmoj problems so hard to submit, it says unused? i m confused, can someone help me on this problem?
It seems user needs to implement the
main
function for this problem.In that case, what's the input style? IschangeH
as operation 1,changeV
as operation 2,escape
as operation 3?