need help in optimization.
Chef is serving dishes at a feast full of colorblind people. He is adding dishes one by one to a long table to form a sequence of dishes; for each dish he adds, we know its color and deliciousness. A person with colorblindness c can only see dishes with colors in the range [c−K,c+K].
You should process Q queries. There are three types of queries:
1 c d: Chef adds a dish with color c and deliciousness d to the front of the sequence.
2 c d: Chef adds a dish with color c and deliciousness d to the back of the sequence.
3 c: Consider a person with colorblindness c. This person must choose an arbitrary contiguous subsequence of dishes on the table (possibly empty) and then eat all the dishes which this person can see. Chef wants to know the maximum possible total (summed up) deliciousness of the eaten dishes.
Note that all the people attending this feast are polite, so no dishes are actually eaten until Chef receives the answers to all of his queries.
Input
The first line of the input contains two space-separated integers Q and K.
The following Q lines describe queries. Each of these lines starts with two space-separated integers b and C, where b denotes the type of this query. If b=1 or b=2, they are followed by a space and an integer d. The value of c for this query is computed as c=C⊕ans, where ans is the answer to the previous query of type 3 or 0 if there have not been any queries of type 3 so far.
Output
For each query of type 3, print a single line containing one integer — the maximum total deliciousness.
Constraints
1≤Q≤2⋅10^5
1≤c,K≤10^9
|d|≤10^3
Subtasks
Subtask #1 (10 points): Q≤2,000
Subtask #2 (10 points): d>0
Subtask #3 (80 points): no additional constraints
Example Input 1
7 1
1 1 1
3 2
3 2
1 3 1
1 1 2
3 3
3 0
Example Output 1
1
0
1
3
Explanation 1
The decoded queries are:
1 1 1
3 2
3 3
1 3 1
1 1 2
3 3
3 1
Example Input 2
4 2
1 1 -3
2 5 5
1 4 4
3 3
Example Output 2
6
You should process Q queries. There are three types of queries:
1 c d: Chef adds a dish with color c and deliciousness d to the front of the sequence.
2 c d: Chef adds a dish with color c and deliciousness d to the back of the sequence.
3 c: Consider a person with colorblindness c. This person must choose an arbitrary contiguous subsequence of dishes on the table (possibly empty) and then eat all the dishes which this person can see. Chef wants to know the maximum possible total (summed up) deliciousness of the eaten dishes.
Note that all the people attending this feast are polite, so no dishes are actually eaten until Chef receives the answers to all of his queries.
Input
The first line of the input contains two space-separated integers Q and K.
The following Q lines describe queries. Each of these lines starts with two space-separated integers b and C, where b denotes the type of this query. If b=1 or b=2, they are followed by a space and an integer d. The value of c for this query is computed as c=C⊕ans, where ans is the answer to the previous query of type 3 or 0 if there have not been any queries of type 3 so far.
Output
For each query of type 3, print a single line containing one integer — the maximum total deliciousness.
Constraints
1≤Q≤2⋅10^5
1≤c,K≤10^9
|d|≤10^3
Subtasks
Subtask #1 (10 points): Q≤2,000
Subtask #2 (10 points): d>0
Subtask #3 (80 points): no additional constraints
Example Input 1
7 1
1 1 1
3 2
3 2
1 3 1
1 1 2
3 3
3 0
Example Output 1
1
0
1
3
Explanation 1
The decoded queries are:
1 1 1
3 2
3 3
1 3 1
1 1 2
3 3
3 1
Example Input 2
4 2
1 1 -3
2 5 5
1 4 4
3 3
Example Output 2
6
Last edited on
i tried using segment trees to find the range of indices in which c-k and c+k are present and find the maximum subsequence sum.
still giving me tle.
please can anybody help me to proceed in right way
still giving me tle.
please can anybody help me to proceed in right way
Ah, that means your approach is very inefficient, and you need to re-think your entire approach.
If this is for a Codechef competition, you should know that the adjudicators are already aware that people are using this forum to cheat in the competition, and have disqualified people for it in the past.
Topic archived. No new replies allowed.