### UtahaSenpai's blog

By UtahaSenpai, history, 10 months ago, ,

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 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

My solution:
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[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.