MojiDeletes
TCO19 SRM 753 · 2019-03-06 · by minimario
Problem Statement
This problem has a time limit of 3 seconds and memory limit of 512 MB.
Arpa has an array A with N elements (indexed 0 through N-1) and Q questions about elements of the array. Each question asks about some non-empty contiguous segment of the array. Arpa initially just wanted to know the bitwise xor of those elements, but that's not what we are doing in this problem.
Mojtaba is Arpa's kind teacher. He wants to give Arpa large answers. Therefore, he decided that whenever Arpa asks a question, he will ignore exactly one of the elements in the specified range. He will always choose the element that maximizes the bitwise xor of the remaining elements in the range. (Note that by definition the bitwise xor of no elements is zero.)
Today, Mojtaba is occupied by preparing a holiday celebration, so you will have to do his job. Compute the answers to all of Arpa's queries, and return their sum.
Both the contents of the array and the queries are generated pseudorandomly. The array A is constructed as follows:
- A[0] = Add.
- For each i from 1 to N-1: A[i] = (A[i-1] * Base + Add) modulo (10^9 + 7).
Parameters L and R for the queries are generated as follows:
- L[0] = QAdd modulo N, and R[0] = (L[0] * QBase + QAdd) modulo N.
- For each i from 1 to Q-1: L[i] = (R[i-1] * QBase + QAdd) modulo N, and R[i] = (L[i] * QBase + QAdd) modulo N.
For query number i, consider all elements of the array A at indices between min(L[i],R[i]) and max(L[i],R[i]), inclusive.
Constraints
- N will be between 1 and 500,000, inclusive.
- Q will be between 1 and 500,000, inclusive.
- Base, Add, QBase and QAdd will each be between 1 and 10^9 + 6, inclusive.
50000 50000 10003 1000003 10003 1000003 Returns: 53447291985080
5 3 10 3 2 2 Returns: 37292
The array A is { 3, 33, 333, 3333, 33333 }. The same numbers in base 2 (with some leading zeros added for readability) look as follows: 0000000000000011 0000000000100001 0000000101001101 0000110100000101 1000001000110101 Query 0 is about elements A[1] and A[2]. Mojtaba will ignore A[1] and answer A[2] = 333. Query 1 is about the entire array. Mojtaba will ignore A[2] and answer (A[0] xor A[1] xor A[3] xor A[4]) = 36,626. Query 2 is the same as query 0. Thus, the correct return value is 333 + 36,626 + 333 = 37,292.
47 42 7654321 1234567 23 10 Returns: 41156782009
500000 500000 1003 1000003 1003 1000003 Returns: 534747796685940
500000 500000 2 1 2 1 Returns: 534618713588573
Submissions are judged against all 18 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MojiDeletes with a public method long long maximumXor(int N, int Q, int Base, int Add, int QBase, int QAdd) · 18 test cases · 2 s / 256 MB per case