ITRIX_D - Board-Queries

no tags 

RishiKumar spends most of his time in solving Querying problems. When solving a 2D Querying problem he got exhausted and he needs the help of someone. Yes he got!! .. Karthi  is in search of his girl and  asked Rishi whether he saw his girl on his way . Rishi replied he knew where she has gone but he will disclose the truth if Karthi solve this Bloody Querying problem. Help Karthi to solve this!!!!

Given two 2D arrays X and Y. Max size of X and Y is 500. (500 x 500)

There are 3 Operations (Three Types of Queries)

A) 0 x1 y1 x2 y2 --- Swaps the contents of the rectangle given by the points (x1, y1) and (x2, y2)  of X and Y.

B) 1 x1 y1 x2 y2 --- Print the sum of all elements in rectangle given by points (x1, y1)  and (x2, y2) of the array X.

C) 2 x1 y1 x2 y2 --- Print the sum of all elements in rectangle given by points (x1, y1)  and (x2, y2) of the array Y.

(Points (x1, y1) and (x2, y2) inclusive)

(x1, y1) –­Top Left point of the rectangle and (x2, y2) –Bottom right point of the rectangle

Input Format:

The first line of the input file contains N – Dimension of the array (It is clear that array is square array i.e. length=breadth). The next N lines contains N integers per line separated by space which are the elements of array X. The next N lines contains N integers per line separated by space which are the elements of the array Y. The next line contains and integer Q –Total number of Queries. Then each of the following Q lines contains the Queries (as per the above operations.)

Constraints: N <=500, 0 <=Xij,Yij <=10^6

Q<=100000 (10 power 5) 

Array indexing start from [1, 1] to [N, N];

Output Format:

Print the result of each Query(There will be output  for query type B and Query Type C)  line by line.

Sample Input:

5

1 2 3 4 5

6 7 8 9 0

1 2 3 4 5

6 7 8 9 0

9 1 2 3 4

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

4

1 1 1 4 4

0 1 1 4 4

1 1 1 4 4

2 1 1 4 4

Sample Output:

80

16

80

Warning: Huge I/O, Make Your I/O  Fast


hide comments
mu_leaf: 2024-05-09 11:23:18

O(Q N \sqrt N) can't get accepted!

Walrus: 2012-08-26 14:50:47

O(Q N \sqrt N) gets accepted whereas O(QN log N) times out !

Anirudh Goyal: 2012-07-28 14:36:19

GOOD ONE!!! ONE POINT FOR THIS QUESTION :)

Shaka Shadows: 2011-03-30 18:25:55

Is a O(Q NlogN) algorithm too slow?

RE: Yes, a O(Q NlogN) algorithm is TOO SLOW.

Last edit: 2011-03-30 19:50:08
Radhakrishnan Venkataramani: 2011-03-29 16:42:47

New Test Cases are added and all solutions are rejudged ..


Added by:Radhakrishnan Venkataramani
Date:2011-03-27
Time limit:5.010s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64