All submissions for this problem are available.
A professor in NITD wants his students to sit in the front rows of the
class, but the students prefer to sit in the back. He has thus devised
a method of seating in which a student will be seated based on
whether the roll number of the student is odd or even. He has asked
your help for this. You will be given an array containing the roll
numbers of the students. The professor will ask you to tell him the
number of students with odd roll numbers, and the number of
students with even roll numbers in a particular range of the array.
However, since the students are your friends, they can ask you to
change their roll numbers in the array. Two students can have the
same roll number, since you don’t have to tell the professor the
actual roll numbers.
The first line of input will be an integer T, denoting the number of
The first line of each test case will consist of two
integers N, the number of students, and Q, the number of queries.
The next line will contain N space separated integers ri, the roll
numbers of the student i for all i from 0 to N-1. The next Q lines will
have Q queries.
Queries are of two types. The type of query will be
specified by a character, which will be P for a query by the
professor, and S for a query by the student.
The query by the
professor will be followed by two numbers x and y in the same line
after the P, separated by a space, which will be the ranges of the
A student query will be followed by two space separated
integers u and w in the same line after the S, where u is the index of
the array, and w is the new roll number which the student wishes to
For each query by the professor, print two space separated integers
in a line, first the number of students in the given range with odd roll
numbers, and then the number of students with even roll numbers.
- 1 <= T <= 10
- 1 <= N <= 10^6
- 1 <= Q <= 1000
- 0 <= ri <= 10^6
- 0 <= x, y, u <= N-1
- 0 <= w <= 10^6
Input: 1 5 3 1 2 3 4 5 P 0 3 S 1 3 P 0 3 Output: 2 2 3 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.