The code block's display formatting seems to be problematic， these two lines changed：

update(1 , 0 , n-1 , x-1 , y)

res = query(1 , 0 , n-1 , x-1 , y-1)

Since the input format was not provided, I'm not sure. If you want change 1-base index to 0-base index, I think it should like this. ~~~~~ for _ in range(m): ch , x , y = map(int , input().split()) if ch == 1: update(1 , 0 , n-1 , x-1 , y) if ch == 2: res = query(1 , 0 , n-1 , x-1 , y-1) print(res[0] , res[1]) ~~~~~

The K-shortest paths algorithm is a new idea, thank you. The value of k can be quite large, but if the edge weights are relatively large and M is relatively small, it may be possible to take a smaller K, which would result in a relatively good time complexity.

Yes, if it is not a complete graph but a sparse graph, then it is as you said.

1. If $$$M$$$ is small, we can use dp to solve it in $$$O(N^2*M)$$$. Define the state $$$dp[i][j]$$$ to indicate whether it is feasible to reach vertex $$$i$$$ with a distance cost of $$$j$$$. Whenever a state changes from infeasible to feasible, add this state to a queue. Each time a state $$$dp[u][j]$$$ is taken from the queue, use it to update all points $$$v$$$ connected to point $$$u$$$ (in a complete graph, that is, all vertices). Then dp[v][j + w[u][v]] ||= dp[u][j]. Obviously, there are $$$N*M$$$ states, and each state updates $$$N$$$ states, so the time complexity is $$$O(N^2*M)$$$. I'm not sure if there is a better way to do it; if there is, please let me know.
2. If $$$M$$$ is large, the problem might be NP-hard. If we consider each edge as a type of product, and the ability to traverse edges repeatedly is similar to the ability to choose an unlimited number of products, then it resembles the complete knapsack problem. I think the original problem is no simpler than this one, so it should also be NP-hard. Of course, I cannot prove this; it's just my guess.

The overall idea is correct; the problem lies in this line of code. fill(arr3.begin(), arr3.end(), 0); I guess your approach is to determine it as invalid and clear arr3 if the palindrome's interval cannot cover [idx1, idx2], but you forgot to add this check.

There's a simpler implementation: remove this line of codearr3[0] = 1;. Then you don't need to check whether to clear it, because if the palindrome cannot cover [idx1, idx2], arr3[0] will equal 0, which means mex=0. In this way, case 3 is the same as the implementation of the first two cases, only using different value of 'left' and 'right'. Then you can use a function like ans = fun(left, right) to unify them.

12:00 UTC (Usual AtCoder time)

Personally I think problem D is easier than problem C; it only took me about half the time of problem C.

Lets consider a sample input R=2,G=2,B=2, thats the fisrt case in your code (R>=G>=B).

The structure is "R_R". Then u fill the blank with G, so u get "RGR". Then, cause B is not 0, then u add B at begin and end. Finally u get "BRGRB", the length is 5. One possible answer can be "RGBGBR", the length is 6.

I think the "R _ R _ R _ R" structure is not necessary.

Thanks for introducing the tool to auto expand includes, that's really cool

some problems to initialize the "lg" array. I modified it and got accept282181464

Runtime error may be caused by division by zero，if nn is 2

nn -= 2;
		
int xx = ss / nn;
int yy = ss / nn + (ss%nn?1:0);