Submit solution
Points:
15 (partial)
Time limit:
1.0s
Java
1.5s
Python
2.5s
Memory limit:
256M
Problem type
is doing a contest. He comes across the following problem:
You have an array of
elements, indexed from
to
. There are
operations you need to perform on it.
Each operation is one of the following:
C x v
Change the-th element of the array to
.
M l r
Output the minimum of all the elements from the-th to the
-th index, inclusive.
G l r
Output the greatest common divisor of all the elements from the-th to the
-th index, inclusive.
Q l r
Letbe the result of the operation
G l r
right now. Output the number of elements from the-th to the
-th index, inclusive, that are equal to
.
At any time, every element in the array is between and
(inclusive).
knows that one fast solution uses a Segment Tree. He practices that data structure every day, but still somehow manages to get it wrong. Will you show him a working example?
Input Specification
The first line has and
.
The second line has integers, the original array.
The next lines each contain an operation in the format described above.
Output Specification
For each M
, G
, or Q
operation, output the answer on its own line.
Sample Input 1
5 5
1 1 4 2 8
C 2 16
M 2 4
G 2 3
C 2 1
Q 1 5
Sample Output 1
2
4
2
Sample Input 2
5 2
1 1 2 2 2
Q 1 4
Q 3 5
Sample Output 2
2
3
Comments
https://dmoj.ca/submission/1143175 has some interesting variable names....
How big is case 15? Why must we optimize our code so much?
My solution using a recursive segment tree with no constant optimizations passes in 1.370s in the worst case.
My hint for you is to answer all queries using a segment tree:
std::unordered_map
is extremely slow.Oh I thought it was always constant time.
I think accessing an unordered_map key is O(1) but it has a really bad constant factor. I could be wrong but believe it is almost as slow as O(logN).
My solution is
but is getting TLE verdict from Case 12 onward. Any tips to optimize?
iam not sure , but may try iterative segment tree (not sure if it's feasible to implement it easily) , also try unordered map or any optimised map for 4th query
I tried using iterative segtree but it's still too slow: https://dmoj.ca/submission/3191595
Ruby won't work here unfortunately, its about as fast as CPython.
Apparently unordered map is too slow.