Scribd
Upload
3 views2 pages

Matrix Update and Query Operations

The document describes a problem involving an N × M matrix initialized with zeros, where operations can update specific rows or query cell values. The Architect provides two types of operations: UPDATE to increment values in a specified row and QUERY to retrieve a cell's value. The implementation requires defining specific functions without standard input/output interaction, and it must handle large matrix sizes and a significant number of operations efficiently.

Uploaded by

Ahmed Gamberli
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views2 pages

Matrix Update and Query Operations

The document describes a problem involving an N × M matrix initialized with zeros, where operations can update specific rows or query cell values. The Architect provides two types of operations: UPDATE to increment values in a specified row and QUERY to retrieve a cell's value. The implementation requires defining specific functions without standard input/output interaction, and it must handle large matrix sizes and a significant number of operations efficiently.

Uploaded by

Ahmed Gamberli
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Matrix

You wake up as usual and, during the day, you start


noticing certain glitches in the world. By the end of the
day, you are sure you are in the Matrix and you want to
get out. The Architect finds you and offers you a way out
if you manage to aid him in a problem.

The Architect has an N × M matrix, where initially all of


the cells are 0. During the day, parts of the matrix are
modified and sometimes the Architect wants to find
something about a certain cell in the matrix.

The Architect tells you that the matrix has N rows and M columns, then he sends you K operations
as follows:

• UPDATE X Y1 Y2: all of the cells on row X between the columns Y1 and Y2 inclusively have
their value increased by 1.
• QUERY X Y: find the value of the cell on row X and column Y.

Task

Because the Architect doesn't trust you completely, this problem is NOT going to be judged the
usual batch way. Instead, you have to implement the following functions:

• void initialize(long long N, long long M)


• void update(long long X, long long Y1, long long Y2)
• int query(long long X, long long Y)

in your source file, with these exact prototypes. You may implement other functions and declare local
and global variables. Your submissions must not interact in any way with standard input/output, nor
with any other file. Do not declare a main function. Your source file will be compiled and linked
together with a source file provided by the committee, which will handle the input/output and will
call the functions your source file has declared ([Link]).

Limits and constraints

• 1 ≤ N, M ≤ 1018
• 0 ≤ K ≤ 500,000
• Rows and columns are numbered starting from 1.
• Time limit: 1.5 seconds
• Memory limit: 128 MB
Subtasks

Subtask Percent of points Additional input constraints


1 20 N, M ≤ 1000; K ≤ 100
2 30 N, M ≤ 100,000; K ≤ 100,000
3 50 none

Sample grader

The problem's web page includes a sample grader, sample_grader.{c,cpp}. You can use the sample
grader to compile and test your implementation of the functions. The sample grader reads the input
file [Link] in the following format:

line 1: NM
lines 2 until EOF: 0 X Y1 Y 2 for update() operations or
1XY for query() operations

For each query() operation, the sample grader prints the return value to the output file [Link].

Example for the sample grader

[Link] [Link] Explanation


25 1 After the last operation, the matrix looks like this:
0224 2
123 1 01000
0215 12221
122
0122
112

You might also like