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?

Problem:

Given an array with *N* integers *A*_{1}, *A*_{2}, ..., *A*_{N} and *M* intervals (*L*_{1}, *R*_{1}), ..., (*L*_{M}, *R*_{M}), you can perform the following operation arbitrary times:

Choose one of the *M* intervals (*L*_{i}, *R*_{i}) and add *A*_{Li}, *A*_{Li + 1}, ..., *A*_{Ri} by + 1 or - 1.

Is it possible to make all *N* integers zero?*N*, *M* ≤ 10^{5}

My solution:

First of all, if all *L*_{i} are different, we can uniquely determine how many times we should perform an operation on the interval (*L*_{i}, *R*_{i}) and whether we should choose + 1 or - 1.

Now, we try to avoid the same left bound. When we find two interval (*L*_{i}, *R*_{i}), (*L*_{j}, *R*_{j}) (*R*_{i} < *R*_{j}) with the same left bound, i.e. *L*_{i} = *L*_{j}, we change the second interval to (*R*_{i} + 1, *R*_{j}) (just imagine what happen if we add 1 to (*L*_{j}, *R*_{j}) and -1 to (*L*_{i}, *R*_{i})). 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*[0] to *bound*[100000], we do something like`bound[bound[i][j]].push_back(bound[i][j+1]);`

It's basically the operation shown in the following picture.

https://drive.google.com/file/d/1q6kYHhXPCIv5N_5qHeWiG6gXrp5KjkkZ/view?usp=sharing

At first, I thought it is a *O*(*n*^{2}) but wasn't able to construct a *O*(*n*^{2}) test case. After coding it, I got an AC and it only runs less than 100 ms. So what's the complexity?