Recently, I tried to solve a problem on Atcoder and came up with a solution. I got accepted but have no idea of its complexity. Does anyone know its complexity and when the worst case happens?
Given an array with N integers A1, A2, ..., AN and M intervals (L1, R1), ..., (LM, RM), you can perform the following operation arbitrary times:
Choose one of the M intervals (Li, Ri) and add ALi, ALi + 1, ..., ARi by + 1 or - 1.
Is it possible to make all N integers zero?
N, M ≤ 105
First of all, if all Li are different, we can uniquely determine how many times we should perform an operation on the interval (Li, Ri) and whether we should choose + 1 or - 1.
Now, we try to avoid the same left bound. When we find two interval (Li, Ri), (Lj, Rj) (Ri < Rj) with the same left bound, i.e. Li = Lj, we change the second interval to (Ri + 1, Rj) (just imagine what happen if we add 1 to (Lj, Rj) and -1 to (Li, Ri)). Because each interval never change its right bound and its left bound is increasing, so we won't do this infinitely.
Here's my implementation: First, we put all right bounds of intervals that have a left bound i into a vector bound[i]. Sort all bound[i]. Starting from bound to bound, we do something like
It's basically the operation shown in the following picture.
At first, I thought it is a O(n2) but wasn't able to construct a O(n2) test case. After coding it, I got an AC and it only runs less than 100 ms. So what's the complexity?